Решение задачки про лягушек

[ermouth]

Как водится в таких задачках, она решается в одно соображение. Решение в конце под катом, а для начала я опишу, как я это решение придумывал.

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

Сначала я пошёл сложным путём и попытался задачу генерализовать топологически, рассматривая примерно вот такие конструкции:

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

Игры с такого рода конструкциями увели меня ещё дальше в сторону примерно на неделю, плюс я тому моменту как раз недавно перечитал Пенроуза с его графическим формализмом и увидел явные аналогии – у него там расшивка скрещивания тоже меняет знак итога. Тем не менее неожиданно рассмотрение задачи на сфере дало мне решение на плоскости.

Я рассматривал случаи, когда все концы лежат в одной полусфере и обратил внимание, что для длинных дуг решение в некотором смысле берётся с обратным знаком в том случае, если заменить дуги на короткие и продолжить короткие дуги так, чтобы условия оставались в силе. Замена дуг на короткие привела меня к мысли, что удобнее рассматривать граничный случай, когда концы дуг лежат на одной геодезической (условном “экваторе”). На плоскость этот случай отображается элементарным образом:

Достаточно в задаче на плоскости продолжить отрезки так, чтобы все их концы лежали на гладкой выпуклой кривой, это и есть главное соображение, которое сразу всё упрощает. (На то, чтобы додуматься до этой простой конструкции, у меня ушло, полагаю, в районе 4-5 часов в несколько приёмов, размазанных на две недели).

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

Докажем (а) – что рассадить всегда можно, если отрезков нечётное количество. Для начала занумеруем точки, двигаясь по окружности, от Т1 до Т[2n], где n – количество отрезков. С какой точки мы будем начинать нумерацию не имеет значения, лишь бы по окружности двигаться.

Пусть мы садим лягушек в нечётных точках (набор Т1, Т3, Т5 и тд). Выберем произвольные две точки из этого набора и обозначим их пересечение как А. На рисунке я выбрал для визуального примера точки Т1 и Т9.

Для доказательства, что лягушки вышедшие из Т[x] и T[y] (обе точки из нашего набора) не встретятся, достаточно показать, что чётность количества пересечений на отрезках АТ[x] и АТ[y] разная. Если это условие соблюдается, то сумма количества пересечений на отрезках АТ[x] и АТ[y] обязательно должна быть нечётная.

На каждом отрезке всего n-1 пересечений по условию задачи. Значит, на двух наших отрезках таких пересечений 2n-2-1 (потому что на двух отрезках одно пересечение общее). Таким образом, если исключить и точку пересечения А, остаётся 2n-4 пересечений.

Это чётное число, оно может получаться или как сумма двух чётных, или как сумма двух нечётных.

Предположим, что оно у нас получилось как сумма двух чётных. Это будет означать, что и в дугу T[x]T[y], и в противоположную дугу T[y]T[x] “упирается” чётное количество отрезков, что очевидно невозможно, потому что количество натуральных чисел между числами одинаковой чётности всегда нечётное (например, число 2 между 1 и 3; 4,5,6 между 3 и 7). Стало быть, противоречие.

Таким образом, остаётся только вариант, что наше количество пересечений без точки А образовано суммой нечётных чисел.

Таким образом, сумма к-ва пересечений на отрезках AT[x] и AT[y] нечётная, чётность к-ва пересечений на AT[x] и AT[y] – разная, что и означает невозможность столкновения.

Утверждение (а) доказано.

Утверждение (б) доказывается похоже, но писанины больше и мне просто лень ) Общая идея – если такая расстановка возможна, нам придётся “воткнуть” между двумя соседними точками на окружности третью, что невозможно, потому что точки и так соседние.