Первый рукописный блог рунета™

Утверждение (b) на сфере, оказывается, неверно. То-есть, существует класс конструкций, в которых расстановка возможна.

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

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

6-я невалидна, блин.

И да, следующий пост точно будет не про лягушек )

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

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

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

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

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

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