Симпатичный международный "гроб"

Пусть S — конечное множество из не менее чем двух точек на плоскости общего положения. Назовем МЕЛЬНИЦЕЙ следующий процесс. Вначале выбирается прямая l, на которой лежит ровно одна точка Р из S. Прямая l вращается вокруг ЦЕНТРА Р до тех пор, пока она впервые не пройдет через другую точку (Q) множества S, которая становится новым центром вращения прямой L по часовой стрелке. Процесс продолжается бесконечно.
Доказать, что можно выбрать некоторую точку Р множества S и некоторую прямую l, проходящую через Р так, что для соответствующей МЕЛЬНИЦЫ каждая точка множества S выступит в роли центра бесконечное количество раз.

Это задача номер 2(!) с IMO нынешнего года (желающие смогут легко найти поиском по IMO 2011 остальные задачи и технические результаты).

Честно признАюсь, что для меня проходимыми на первый взгляд заданиями являются только четыре. Шестую геометрию я даже не смотрел, а вот эта "мельница" меня сильно зацепила.

Во-первых, условие интересное и неочевидное. Во-вторых, я, к своему стыду, за два дня так и не понял, как решать эту задачу. Полярным преобразованием, что ли ?

А если так: строим выпуклую оболочку — это множество S1. Затем выпуклую оболочку множества S\S1 — это S2, и.т.д. В итоге получим конечное число вложенных многоугольников и, может быть, точку внутри "самого внутреннего" многоугольника.

Возьмем P = этой точке, если она есть, либо P = любой вершине самого внутр. многоугольника, если этой точки нет. Возьмем l — любую прямую, проходящую через P и внутренние точки самого внутр. многоугольника.

Тогда "мельница" — прямая — всегда будет проходить через внутренность всех многоугольников и угол наклона будет меняться монотонно до + бесконечности. Весьма правдоподобно, что такая мельница будет заметать все точки плоскости, кроме некоторой области внутри самого внутреннего прямоугольника, бесконечное число раз.

Осталось все строго доказать или найти лажу.


А какое решение запостили авторы?

Лажа в том, что прямая не обязательно всегда будет проходить через внутренность всех многоугольников. Контрпример можно придумать даже с двумя многоугольниками: внутренний — правильный треугольник, наружный — подходящим образом расположенный многоугольник с достаточно большим количеством вершин, прямую провести через вершину треугольника очень близко к другой его вершине.

Вот тут, как раз, лажи, скорее всего, нет. Нарисуйте картинку — поймете, почему Ваш контр-пример неверен (направление вращения, по условию, не меняется — меняется только центр вращения).

Если буквоедстовать — прямая будет проходить через внутренность всех многоугольников, кроме самого внутреннего.

Самый внутренний — это многоугольник, отрезок или точка.

И прямая будет проходить либо через внутренность этого "самого внутреннего", либо через вершину "самого внутреннего" — что не мешает решению задачи.

Если "самый внутренний" — отрезок или точка, прямая, в процессе движения может выйти за его пределы. Но это не страшно, так как.

Пусть L0 — первая прямая, L1 — прямая со след. центром вращения, и.т.д.

Тогда среди прямых L0,L1,L2,....,..... лишь конечное число различных (т.к. прямая определяется парой точек, пар точек — конечное число).

Поэтому последовательность зацикливается: L0,....,Lm,...,Ln,Lm,....,Ln и.т.д.
Так как никакие три точки не лежат на одной прямой, следовательно L(m-1) однозначно определяется по Lm, поэтому последовательностть зацикливается с самого начала: L0,L1,...,LT,L1,....LT,,,,, и.т.д.

Итого — если мельница побывала в точке S — она придет в нее бесконечное число раз.


Так что неприятностей с "самым внутренним" как точка нет, а с "самым внутренним" как отрезок устраняются, если взять L0 близко к этому отрезку и проходящую через его конец. Тогда L1 пройдет через оба конца (если ориентация выбрана верно, разумеется).


Ну а то, что эта мельница заметет все прочие точки — несложно доказать, полагаю.

Несложно, наверное, только как?
Опять же, может быть и не докажется.
Может, основываясь на ваших мельничных постулатах, доказать основное утверждение как-то комбинаторно?
Ну, в плане, например, что различных вариантов мельницы будет столько, что уж обязательно один из них будет искомым

Комбинаторно — муторно, плюс много сложностей технического плана.

Так что надо дожимать геометрические соображения ориентируемости и выпуклости. Или использовать конечность множества углов и расстояний плюс какие-то дополнительные структуры — например лучи из "центральной точки" в остальные точки множества S.

Кстати, Мутафян в #3 был прав — контр-пример можно построить на 7-ми точках, плюс вообще прямая может временно подниматься по орбитам хоть до внешней — так что сорри.

Итого — имеем только цикличность мельницы (следствие — если точка плоскости заметается, то бесконечное число раз) и разбиение на оболочки.

А если самый внутренний — многоугольник с числом вершин больше двух? :)

Ну какая разница, где у нас возникнут проблемы — в заметании вершин самого внутреннего или дальше: ни то ни другое не доказано:)

Просто, когда писал #2 — поленился нарисовать картинку, соотв. думал, что главный затык — бесконечное заметание вершин самого внутреннего в случае, если он вырожден. (был уверен, что никуда прямая из внутренности всех многоугольников не денется:) ).

Вы бы лучше не критиковали, а решение предложили — я уже потратил больше 40-ка минут, что в условиях реальной олимпиады — однозначно нерешенная задача.

Я не заметил, что в #8 Вы признали ошибку, потому и критиковал.

Я пока тоже не знаю, как решить. Как придумаю — напишу. Чтобы такие задачи за 40 минут решать, нужно несколько лет тренироваться в сверхинтенсивном режиме, набирать "спортивную форму". Так что Вы себя по олимпиадному времени не оценивайте.

Есть олимпиадники тренированные, есть — умные сами по себе. Из первой категории редко получаются потом математики.

Данная конкретная задача, по-моему, тренировок и специальных знаний не требует: "тренировка" в данном случае сведется к тому, решал ли раньше человек конкретно эту задачу или нет.

Себя я уж точно по олимпиадному времени не оцениваю — спорт меня не интересует.

Кстати если посмотреть на статистику, эта задача оказалась сложнее, чем третья, вопреки многолетней традиции международных олимпиад:

http://imo-official.org/year_statistics.aspx?year=2011

Из российской команды её до конца никто не решил:

http://imo-official.org/team_r.aspx?code=RUS&year=2011