Математикадан 52-ші халықаралық олимпиада, 2011 жыл, Амстердам


Жазықтықта кемінде екі нүктеден тұратын ақырлы нүктелердің $S$ жиыны берілген. $S$ жиынынан алынған кез келген үш нүкте бір түзудің бойында жатпайды. Мынадай үрдісті диірмен деп атаймыз: ол $S$ жиынымен тек қана бір ортақ $P$ нүктесі бар $\ell $ түзуінің көмегімен басталады; біз осы түзуді сағат тілімен $P$ центрін айналдыра, түзу үстінде $S$ жиынының басқа бір нүктесі пайда болған мезетке шейін бұра береміз; бұл нүкте, оны $Q$ деп белгілейік, осы мезеттен бастап жаңа центр ретінде қарастырылып, енді түзуді сағат тілімен $Q$ нүктесін айналдыра, түзу үстінде $S$ жиынының басқа бір нүктесі пайда болғанша бұра береміз. Бұл үрдіс ақырсыз жалғаса береді.
$S$ жиынының бір $P$ нүктесі және осы $P$ нүктесі арқылы өтетін бір $\ell $ түзуі үшін $\ell $ түзуінің көмегімен басталған диірмен үрдісінің орындалу барысында $S$ жиынының әрбір нүктесі ақырсыз көп рет центр рөлін атқаратынын дәлелдеңдер.
посмотреть в олимпиаде

Комментарий/решение:

  2
2020-11-18 21:25:15.0 #
  1
2023-12-11 19:34:51.0 #

В ютубе есть решение канала 3Blue1Brown

  7
2023-12-05 10:23:20.0 #

сначала вы берете выпуклую оболочку и называете этот многоугольник S1, затем вы берете $S_1$ из $S$, берете выпуклую оболочку и называете этот многоугольник $S_2$, и продолжаете делать это, пока не получите $S_1, S_2, S_3, \dots, S_n$ и осталось 0, 1 или 2 очка. Теперь выберем линию $l$ такую, чтобы она содержала точки внутри $S_1, S_2,\dots, S_n$. Теперь мы перемещаем l до тех пор, пока он не встретит одну из точек $S$, но только одну, если он касается 2 точек в $S$, мы снова генерируем $l$ под другим углом (у него все равно будут точки внутри многоугольников, в на самом деле он будет содержать сегменты внутри многоугольников) и начните с процесса.

Случай 1: после удаления последней выпуклой оболочки осталось 0 очков:

Sn — многоугольник: легко видеть, что для каждого многоугольника $S_i$ линия l всегда будет иметь точки внутри этого многоугольника, потому что единственный способ «выйти» из многоугольника — это встреча двух последовательных точек $v_1$ и $v_2. $ многоугольника и выход из многоугольника, но если он касается $v_1$, а затем $v_2$, это означает, что $v_2$ идет первым по часовой стрелке, поэтому линия затем войдет внутрь многоугольника. (Я не очень хорошо объясняю свои решения на английском языке. Если вы чего-то не понимаете, дайте мне знать, и я попытаюсь объяснить это еще раз). Поскольку угол линии будет вращаться вечно по часовой стрелке, то каждая точка в $S_i$ будет встречаться линией бесконечно много раз для каждого многоугольника Si, потому что найдется пара точек $(v,w)$ такая, что линия встретится с $v$ и $w$ одновременно бесконечно много раз (после второго раза она встретит их те же движения, что и в первый раз, снова начнутся, приводя к кругу), и в этом цикле каждая точка встретится по крайней мере однажды (это не очень сложно доказать)

Случай 2: после удаления последней выпуклой оболочки осталось 1 или 2 очка:

В этом случае мы используем тот же алгоритм, что и в предыдущем случае, мы забываем об этих 1 или 2 точках и видим, что каждая точка внутри $S_n$ будет встречена хотя бы один раз в процессе. Итак, мы начинаем процесс до тех пор, пока не будет достигнута одна из 1 или 2 точек внутри $S_n$. Если это всего лишь одна точка, идея та же, потому что линия будет вращаться вечно, и пара точек будет встречена дважды, следовательно, бесконечно много. раз, поэтому каждая точка в каждом многоугольнике будет встречаться бесконечно много раз, и точка внутри тоже. Если внутри есть две точки, то мы должны доказать, что обе точки будут встречены в процессе, но это легко, потому что, поскольку обе точки находятся внутри $S_n$, а линия в каждый момент имеет отрезок внутри $S_n$, и линия достигает одной и той же позиции бесконечно много раз, то обе точки будут встречаться бесконечно много раз, потому что между моментами $M_1$ и $M_2$, когда линия имеет одно и то же положение, каждая точка внутри $S_n$ будет встречаться с линией (это легко докажи это, чтобы я не делал этого, пока кто-нибудь не попросит меня об этом).

  0
2023-12-06 20:25:56.0 #

Bruh

  0
2023-12-08 17:33:36.0 #

Хорошее решение что такого

  0
2023-12-09 14:33:10.0 #

закройся