Математические байки

С одной стороны — действительно, φ^2=φ+1, так что таких позиций получается по одной на каждой диагонали: [n φ^2]=[n φ] + n. С другой — возникает вопрос: а почему при этом в каждом столбце будет по одной проигрышной позиции — то есть почему каждое натуральное число представляется либо как [n φ], либо как [n φ^2], причём только одним способом? (Скриншот — опять же, кусочек из статьи И. В. Арнольда)

/2

А вот — удивительный! — ответ: координаты проигрышных позиций имеют вид ([n φ], [n φ^2]), где [.] — целая часть, а φ=(√5 +1)/2 — золотое сечение (в статье оно обозначено через τ)

Вот тут он формулирует задачу и переходит к проигрышным позициям ("основным парам").

Давайте я закончу этот рассказ — тут совсем немного осталось. Во-первых, для подстановочного слова есть способ его "считывать" через поворот окружности и то, на какую из двух дуг попадает очередная итерация начальной точки: см. тут+ниже. Во-вторых, отсюда уже можно увидеть, что "линия" проигрышных позиций в игре "ферзя в угол" идёт под углом наклона, равным золотому сечению. Потому что именно с таким отношением идут буквы A и B в слове Фибоначчи, а применение преобразования "каждое А соответствует сдвигу на (2,3), каждое B — сдвигу на (1,2)" приводит к такому же отношению y:x. В-третьих, и это отдельно интересно — оказывается, что для проигрышных позиций есть явная формула. И я тут хочу процитировать статью И. В. Арнольда (не Владимира Игоревича — а его отца!), "Об одном свойстве числа τ=(√5 +1)/2", вышедшей в 1936 году в 8 выпуске "Математического просвещения" — ещё первой серии этих сборников!

Если мы перепрыгиваем через вертикали на расстоянии 3 (то есть стартующие из проигрышных позиций, симметричных A-звену), то мы делаем один A-прыжок (2,3), перепрыгивая через вертикаль, а потом один B-прыжок (1,2), подходя к следующей вертикали. А если через вертикали на расстоянии 2 (то есть стартующие из проигрышных позиций, симметричных B-звену), то мы делаем только один A-прыжок (2,3), перепрыгивая через вертикаль, и мы уже вплотную подошли к следующей вертикали. Вот мы и получили правила замены — А заменяется на AB, а B заменяется на A!

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

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

Видно, что слово одно и то же. А что это за слово? Это — слово Фибоначчи, а на картинке выше — кусочек из (начинающейся с его определения) статьи "Слова на ленте" в "Квантике". Это слово получается так: мы начинаем со слова из одной буквы "A", после чего в каждом написанном слове заменяем A на AB, а B на A. Получается последовательность слов A AB ABA ABAAB ABAABABA..., которые все продолжают друг друга — и потому являются началами бесконечного слова; это и есть слово Фибоначчи.

А ещё можно их последовательность закодировать, превратив в слово из букв "A" (большой прыжок) и "B" (маленький прыжок). Взяв эту картинку и пройдясь по ней, мы получим — ABAABABAABAABABAAB +(хвостик торчащего дальше длинного прыжка А) И...

в) А ещё видно, что соседние позиции в верхней цепочке отличаются либо на сдвиг на (2,3), либо на сдвиг на (1,2). И на этой картинке первые звенья-сдвиги мы раскрасили красным, а вторые — синим.

а) Становится видно, что проигрышные позиции выстраиваются в две симметричные "цепочки"; б) А ещё поле зрения оказывается заполненным линиями из выигрышных позиций; давайте эти линии спрячем, а оставим только проигрышные позиции и ломаную, которая "верхнюю" цепочку соединяет

Ну или запрячь компьютер — пусть он считает, он железный (ну или кремниевый...) —

Эта задача хороша тем, что в ней можно "поработать руками" — просто взять большой лист клетчатой бумаги, на нём последовательно нарисовать выигрышные и проигрышные позиции, и посмотреть, "что происходит":

И ответ на исходный вопрос задачи — выигрывает начинающий, любым из ходов на c5, d1 или e3. Но — а что, если доска будет большего размера? Давайте только, для удобства рисования, перевернём доску — пусть ферзь идёт в левый нижний угол. То есть — разрешено его двигать влево, вниз, и по диагонали влево-вниз. Если пронумеровать строки и столбцы, начиная с 0, то эта игра оказывается эквивалентной игре цзяньшицзы: есть две кучки камней, за один ход можно взять сколько угодно камней из одной из кучек или поровну из обеих; кто не может сделать ход, проиграл (или — побеждает тот, кто взял последний камень). И вот статья о ней в "Кванте" в 1984 году: Матулис А., Савукинас А., Ферзя — в угол, ``цзяньшицзы'' и числа Фибоначчи

Ну и разбор на доске 8x8 завершается тем, что клетки d1 и a4 проигрышные:

Значит, e3 и c5 проигрышные, ну а те, откуда на них можно пойти — выигрышные:

Поэтому с любого из полей, куда можно туда пойти — надо туда ходить и выигрывать: