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

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

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

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

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

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

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

( Read more... )