Алгоритм "Мельница"


Встретил интересную задачу, которая была на Международной Олимпиаде по математике (IMO) в Амстердаме в 2011 году.

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

Вопрос: докажите, что мы можем выбрать первоначальную точку вращения и провести прямую так, что каждая из точек на плоскости будет использоваться в качестве точки вращения мельницы бесконечное количество раз.

Автор задачи: Geoffrey Smith, UK.

Конечно же, вы можете найти ответ в сети. Но думаю кому–то будет интересно решить самому, учитывая, что у задачи есть достаточно несложное и элегантное решение.
98
98
Подписаться на Dirty
Не то сообщество явно. :)
EZRider: Ну, во–первых, это просто красиво.
бесконечное множество точек... хотя бы счётное или прямо континуум может быть? чёт интуитивно сомневаюсь что прямая обойдёт бесконечно количество точек более одного раза
Посмотрите на снежинку Коха. Несмотря на визуальные грницы, ее длина (периметра) — бесконечна. И несложно представить, как она пересекается вращающейся прямой, обходя все её точки за оборот.

image
moo: Ваш пример не соответствует условию задачи, в котором три точки не должны лежать на одной прямой, поэтому некоторые точки не могут вообще быть точками вращения.
sticker: А это и не имеет отношения к задаче. Это чтобы показать, что интуитивное не всегда соответствует действительности.
moo: moo: если только для это был приведён пример, то спору нету. я ведь стал пытаться найти как тут прямая вращается и проходит все точки по условию задачи (а они тут не выполняются, как указал автор). Интуиция — это эвристика, она не может быть точной. Тем не менее, её можно тренировать.
cheesycheese: Интуиция — это когда мозг подсказывает без участия сознания, но на основе опыта. Опыт может соответствовать явлению, а может быть просто похож. Как эта снежинка похожа на замкнутый контур определенной длины.
наши умозаключения по отношению к интуиции не противоречат друг другу, ваш комментарий раскрывает реализацию оной в человеческом мыслительном процессе, мой — сущность, из которой вытекает не точность от применения интуиции.

Тем не менее я так и не понял фразу "И несложно представить, как она пересекается вращающейся прямой, обходя все её точки за оборот.", что под ней имелось ввиду, раз не то, о чём говориться в изначальной задаче?
moo: "пересекается вращающейся прямой" в смысле как задаче в посте?
moo: Точно бесконечна? Количество элементов стремится к бесконечности, а их размер сремится к нулю. Длина на первый взгляд конечна.
42na: Точно. А еще у нее дробная размерность.

Кривая Коха нигде не дифференцируема и не спрямляема.
Кривая Коха имеет бесконечную длину.
Кривая Коха не имеет самопересечений.
Кривая Коха имеет промежуточную (то есть не целую) хаусдорфову размерность, которая примерно равна 1,26 поскольку она состоит из четырёх равных частей, каждая из которых подобна всей кривой с коэффициентом подобия 1/3.
42na: На каждом следующем шаге каждый из кусочков становится ровно на четверть длиннее, так что длина всей линии растет в геометрической прогрессии.
cheesycheese: в условии задачи сказано про конечное множество точек, в случае с бесконечным вы правы, прямая не сможет перейти в начальную точку и неважно какая мощность — счетная или континуальная
Losh_Ok: автор при публикации допустил ошибку, и написал что множество точек бесконечно. Ниже в комментариях об этом есть.
Возьмите любой треугольник, точки будут вершинами и любая четвертая внутри.

Если прямая начинает вращаться вокруг одной из вершин, она никогда не попадет внутрь.

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

Следовательно утверждение в ОП посте ложно.
mrWermut: по условию мы это выбираем самостоятельно и просят доказать что можно выбрать такую точку и провести такую прямую, что все точки "поучаствуют"
smartov: Вот я вам четко показал частный случай, когда это невозможно. Следовательно эта "теорема" фейковая, по крайней мере в изложении автора поста.
mrWermut: Возьмите карандаш, нарисуйте треугольник и точку внутри, и вы поймете, что ваше утверждение "Если начальной точкой выбрать центральную, то прямая на первой вершине зациклится вокруг вершин и в центр не вернется." — ошибочно.
sticker: даже если не на первой вершине, то в любом случае через пару итераций прямая будет ходить только по вершинам.
mrWermut: погодите, а зачем же вы свой комментарий удалили? Странный какой–то спор получается.
давайте такой вариант, тоже интересно.
mrWermut: Ээээ, вы чего. Теорема нормальная. Просто нужно, чтобы прямая разделяла хотя–бы две точки.
kunix: Нет, этого недостаточно:
image
unC0Rr: Хм, да, похоже, недостаточно.
kunix: Возможно, нужно делить на две равные части.
unC0Rr: Ну ведь иногда равных частей не может быть, а решение есть.
Прям интрига :)
kunix: провести прямую через выбранную точку так, чтобы с обоих сторон прямой было одинаковое количество точек N или с одной N, а с другой N+1.
sticker: В случае нечётного числа проводить через одну точку, в случае чётного — через две.
unC0Rr: Количество точек с каждой стороны прямой на каждом втором шаге — инвариант, доказывается тривиально. Интуитивно, если делить не поровну, то со стороны, где меньше точек, каждая обязательно в какой–то момент окажется с другой стороны прямой, а со стороны, где точек более чем на две больше — гарантированно окажутся точки, ни разу не побывавшие на прямой. Над доказательством завтра подумаю.
unC0Rr:
То есть, количество точек с каждой стороны прямой (а точнее, вектора, ведь нам нужно "лево" и "право") — инвариант (когда прямая пересекает только одну точку).

А, значит, по углу вектора относительно вертикали мы можем однозначно определить точку, через которую он проходит.

Итак, проводим вектор через одну из точек, чтобы он делил остальные точки как (N+1,N) или (N,N) и запускаем процесс.

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

Ждем поворота вектора на 180 градусов.

В случае (N,N) вектор проходит через ту же точку, но "правые" точки стали "левыми" и наоборот.
Значит, он побывал во всех точках.

В случае (N+1,N) вектор проходит через "соседнюю" (в смысле проекции на перпендикуляр к вектору) точку со стартовой.
Вобщем, он тоже побывал во всех точках.

Собственно. вроде все.
Однако, мне кажется, оригинальное решение было длиннее.
Тут наверняка ошибка :) Но я не вижу.
kunix: В случае (N,N) вектор проходит через ту же точку, но "правые" точки стали "левыми" и наоборот.

Совсем не очевидно.
unC0Rr: Эм, ну а как иначе? С одной стороны N, с другой стороны N.
Будем параллельно перемещать вектор.
У нас нет других вариантов, кроме стартовой точки.
Иначе будет (N–1,N+1) или еще как.
kunix: Не видно, из чего следует, что не найдётся одной–двух точек, которые прямая обогнёт, как в примере выше.
unC0Rr: То есть, не очевидно утверждение "Значит, он побывал во всех точках.", так?

В случае (N,N) вектор "замел" всю плоскость.
В случае (N+1,N) он "замел" всю плоскость, за исключением узкой полосы, в которой нет точек.
kunix: за исключением узкой полосы, в которой нет точек.

А где доказательство, что в этой узкой полосе не найдётся, к примеру, двух точек?
unC0Rr:
Я не расписывал, т.к. должно быть вполне очевидно.
При старте расположим вектор так, чтобы "справа" было N точек, а "слева" N+1 точка.
После поворота на 180 градусов, "справа" все еще N, "слева" все еще N+1, т.к. инвариант.
Но вектор повернулся на 180 градусов, поэтому "лево" стало "право".
То есть, у нас было N+1 ↑ N, а стало N ↓ N+1.
Прямая сместилась на одну точку влево.
Ясно, что между исходным положением прямой и конечным нет точек.
kunix: Хм, я согласен, что это не очевидно и надо доказывать.
Но в данном случае скорее всего верно.
kunix: Да ладно, это в уме доказывается.
Доказываем, что при любой конфигурации точек при любом положении вектора, он "заметает" на заданной полуплоскости такой–то угол.
Надо рассмотреть два варианта.
A — следующая точка вращения на другой полуплоскости.
B — следующая точка вращения на данной полуплоскости.

862x257 px
mrWermut:
Еще раз. Просто нужно, чтобы прямая разделяла хотя–бы две точки.
А этот пример я задолго до вас построил для smartov.
А это разве не очевидно? Прямая вращается и непрерывно делит пространство надвое, значит она так или иначе пересечет все точки на плоскости, а поскольку три не лежат на одной прямой, то каждая успеет побывать ее центром ващения. Как доказать формулами — хз, я не настоящий сваршик.
moo: у математиков "это же очевидно" не прокатит в качестве доказательства. В том числе и потому, что хитрые математики придумали достаточно большое количество задач, в которых "очевидное" решение является неверным.
airfoilkirra: Хмм, остальные слова для вас ничего не значат? Задача: доказать, что сумма углов треугольника равна 180 градусов. Ответ: это же очевидно, если провести через любую вершину прямую, параллельную противоположной стороне, то смежные с вершиной углы будут равны углам двух других вершин, а в сумме они образуют ту самую прямую, которая есть 180 градусов.
moo: Хорошо, но тогда сначала нужно доказать что смежные углы равны ^_^
W1nd: И что пространство евклидово.
moo: значат, просто я не увидел в нем математически строгого рассуждения.
Как–то с формулировками у Вас не очень строго.
Предположим, что на плоскости находится бесконечное множество точек.
Любая геометрическая фигура, кроме самой точки и есть множество точек.

Прямая, проведенная через одну из них, поворачивается до тех пор, пока на ее пути не встретится любая точка. Тогда эта точка становится новым центром вращения. Прямая (мельница)
Старик Евклид (мы же про другие геометрии не говорим?) утверждал, что через две любые несовпадающие точки на плоскости можно провести одну и только одну прямую. То есть Ваш алгоритм никогда не начнет работать, ибо пямая это тоже бесконечное множество точек.

Может не стоило "пересказывать" условия задачи своими словами, а дать строгую формулировку?
Zanoz: В конце есть ссылка, по которой верхний абзац — это строгая формулировка.
sticker: мне кажется или по ссылке в строгой формулировке имеется ввиду конечное множество точек (состоящее минимум из двух), а у вас бесконечное?
cheesycheese: упс, виноват, исправил.
sticker: В формулировке по ссылке первое предложение говорит о конечном множестве точек: "Let S be a finite set of at least two points in the plane". А вы пишете о бесконечном множестве. Это разные задачи.
grauwelf: меня уже поправили, спасибо. В тексте поста — исправлено.
Разве не очевидно что при таких условиях единственный вариант при котором точка никогда не будет служить центром вращения может быть только в случае если эта точка принадлежит прямой между двумя другими точками, а по условиям задачи нет трёх точек на одной прямой.
smartov:

Контрпример:
Представьте себе точки, равномерно распределенные на окружности.
И одну точку внутри окружности.
Проведите прямую через любую точку на окружности так, чтобы все остальные были с одной стороны.
kunix: контрпример есть два стула...
при чем тут вообще ваш контрпример?
smartov: Что–то вы вашему нику не соответствуете...
Это контрпример к вашему "разве не очевидно".
Я выбрал конфигурацию точек и прямую, при которых одна точка никогда не будет центром вращения.
kunix: либо вы неверно поняли условие либо вы неверно описали пример. Какая точка в вашем примере не будет центром вращения?
smartov: Которая внутри окружности.
Прямая будет ходить по хордам, но в центр никогда не доберется.
kunix: вращающаяся прямая описывает всю плоскость. Это одно из возможных определений плоскости. Вращающаяся прямая не может не пройти через точку, которая лежит на этой плоскости. Так что если центр вашей окружности никогда не станет центром вращения, то только если она лежит на прямой с другими двумя точками на окружности, а по условию задачи это не так.
smartov: Боже, ну за что мне это....
Прямая вращается до встречи с другой точкой.
Вам GIF–ку нарисовать или сам догадаетесь?
kunix: прямая не перестаёт вращаться после встречи с точкой. Центр вращения не принципиален, прямая всегда описывает одну и ту же плоскость. Но если вам хочется визуализировать свою ошибку то ради бога, очень хочется увидеть как ваша вращающаяся прямая не проходит через точку лежащую на плоскости вращения. Отправлю разработчикам учебников геометрии.
smartov: извините, не умею в анимацию, да и в статику не очень
800x600 px
cheesycheese: класс! признаю такой вариант я себе не представлял. шикарно, спасибо. хотя как заметили ниже действительно достаточно и треугольника и прямой проходящей только через одну его вершину, и точку "недостижимости" поставить внутри него.
smartov: Всё так. Но это не доказывает, что каждая точка может быть центром вращения бесконечное количество раз.
sticker: вращающаяся прямая описывает плоскость значит априори тронет все точки, а т.к. трёх на одной прямой нет, то каждая побудет центром вращения хоть один раз за оборот.
smartov: эй, я из прошлого, ты был не прав! ниже пример
>Предположим, что на плоскости находится бесконечное множество точек
Читайте оригинал внимательно.
А то я все думаю, а что же будет, если "мельница" встретит на своем пути точку сгущения.
Как следующая точка определится.
Вроде простая задача.
Надо выбрать точку X в пространстве, не совпадающую с заданными, и построить вокруг нее окружность.
Нужно, чтобы на ней не было дуг >=180 градусов между проекциями. (TODO: доказать, что это всегда возможно).
Далее мы заменяем заданные точки проекциями относительно X на эту окружность.
Вроде бы очевидно, что задача не меняется.
Теперь выбираем прямую, которая имеет хотя бы две точки с разных сторон.
И запускаем процесс.
Прямая будет "шагать" туда сюда и все норм.

Это если есть хотя бы три точки.
Если точки две или одна, все очевидно.
kunix:
>TODO: доказать, что это всегда возможно
Берем X внутри любого треугольника, построенного на трех заданных.

Надо еще, чтобы X не лежала на одной прямой с любыми двумя заданными.
Но это просто.
как–то так:
на вертикальной и/или горизонтальной плоскости не должно быть расположено больше одной точки?
Интуитивно понимаю как определить начальный центр вращения: из заданных точек проводятся окружности с радиусом, равным отрезку до максимально удалённой от описываемого центра точки. Окружность с минимальным радиусом определит отправной центр вращения.
ipsy: Если я правильно понял, то вот контрпример:
600x441 px
Прочёл ещё раз постановку задачи и парирую, Ваш контрпример не удовлетворяет условию: "докажите, что мы можем выбрать первоначальную точку вращения и провести прямую ТАК, что каждая из точек на плоскости будет использоваться в качестве точки вращения мельницы бесконечное количество раз." Прямая проводится через одну точку, в этом случае на Вашем рисунке можно провести прямую из зеленой точки между второй зеленой и красной точками, и условие соблюдается.
ipsy: Это контрпример к алгоритму определения начальной точки. Понятно, что условиям начальной задачи удовлетворит прямая, проходящая через красную точку. Но по алгоритму выбирается зелёная точка.
unC0Rr: Понятно, что условиям начальной задачи удовлетворит прямая, проходящая через красную точку. Нет. Я описал пример с начальным центром в зелёной точке. Мой подход с радиусами я не доказал, я просто опровергаю Ваш контрпример.
unC0Rr: Если следовать условию задачи, важно не определение начального центра вращения, а правильное положение прямой на плоскости. С использованием Вашего же примера можно показать что красная точка не удовлетворяет условию при вертикально ориентированной прямой через неё.
Ещё ни один математик не доказал, что мне пригодилась в жизни геометрия.