52-я Международная Математическая OлимпиадаНидерланды, Амстердам, 2011 год

Пусть $S$ — конечное множество точек на плоскости, содержащее хотя бы две точки. Известно, что никакие три точки множества $S$ не лежат на одной прямой. Назовем мельницей следующий процесс. Вначале выбирается прямая $\ell $, па которой лежит ровно одна точка $P\in S$. Прямая $\ell $ вращается по часовой стрелке вокруг центра $P$ до тех пор, пока она впервые не пройдет через другую точку множества $S$. В этот момент эта точка, обозначим ее $Q$, становится новым центром, и прямая продолжает вращаться по часовой стрелке вокруг точки $Q$ до тех пор, пока она снова не пройдет через точку множества $S$. Этот процесс продолжается бесконечно.
Докажите, что можно выбрать некоторую точку $P$ множества $S$ и некоторую прямую $\ell $, проходящую через $P$, так, что для мельницы, начинающейся с прямой $\ell $, каждая точка множества $S$ выступит в роли центра бесконечное число раз.

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

Решение

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

сначала вы берете выпуклую оболочку и называете этот многоугольник 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$ будет встречаться с линией (это легко докажи это, чтобы я не делал этого, пока кто-нибудь не попросит меня об этом).

Bruh

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

закройся