Ферзь и цзяньшицзы
Виктор Клепцын
«Квантик»№11, 2023
На кружке Мике и Жене попалась такая задача:
На шахматной доске на поле f8 стоит ферзь. За ход его можно передвинуть на любое число полей влево, вниз или по диагонали «влево-вниз». Выигрывает тот, кто поставит ферзя на поле a1.1
— Всё понятно, — сказала Женя. — Такие задачи называют задачами на выигрышные и проигрышные позиции. В каждой позиции кто-то выигрывает, как бы ни играл оппонент. Это или начинающий, или его противник. И это можно последовательно выяснять, начиная с возможных финальных позиций. Когда партия уже окончена — известно ведь, кто победил!
— Партия оканчивается, когда ферзь стоит на a1, — подхватил Мика. — И если игрок его там видит при своём ходе, то туда его поставил противник, а сам игрок, чей сейчас был бы ход, проиграл. Это позиция проигрышная. А во всех местах, откуда можно сделать ход на a1, позиция ферзя выигрышная: если я вижу возможность выиграть за один ход, я выиграю!
— Верно, — одобрила Женя. — Это такое общее правило: если из позиции можно сделать ход, отдав противнику проигрышную позицию, то она выигрышная. А что, если ферзь стоит на поле c2?
— Оттуда есть четыре хода: на a2, на b2, на b1 и на c1, — начал перебирать варианты Мика. — Но куда ни пойди — противник после этого может выиграть!
— Правильно, — подтвердила Женя. — Поэтому это позиция для начинающего проигрышная. И это второе общее правило: если из позиции можно пойти только в выигрышные, то она проигрышная.
— Тогда поля c2 и b3 — проигрышные по второму правилу. А все те, из которых в них можно пойти, — выигрышные по первому, — продолжил Мика (рис. 1).
Отметив эти выигрышные поля, Мика и Женя быстро закончили разбор задачи: поля f4 и d6 проигрышные, те, откуда на f4 или d6 можно пойти, — выигрышные. И, наконец, h5 и e8 — проигрышные (рис. 2).
Рис. 2. Задача о ферзе: окончание
— А наш ферзь где начинал? — спохватилась Женя.
— На полe f8, — посмотрел в условие Мика. — Ну, это просто. Поле выигрышное — то есть выигрывает начинающий. А нужно ему пойти на любое из проигрышных полей — e8, f4 или d6. И дальше отдавать каждый раз противнику проигрышную позицию.
И они перешли к следующей задаче в листочке:
В игре «цзяньшицзы» есть две кучи камней. Два игрока ходят по очереди; за один ход можно или взять любое количество камней из одной из куч, или взять поровну (и тоже любое количество) камней из обеих куч. Выигрывает тот, после чьего хода камней не осталось. Кто выигрывает при правильной игре?
— Сколько у кого камней исходно, не сказано, значит, нужно дать ответ в зависимости от их количества, — начала проговаривать Женя. — Давай для наглядности сделаем таблицу: столбцам будет соответствовать, сколько камней в первой куче (0, 1, 2 и т. п.), а строчкам — сколько во второй. И будем отмечать, какие клетки выигрышные, а какие проигрышные.
— Партия заканчивается, когда камней нет, и для того, чей сейчас ход, это поражение. То есть клетка (0,0) проигрышная, — подхватил Мика. — А из каких позиций можно выиграть за один ход?
— Это просто, — продолжила Женя. — Либо камни остаются только в одной кучке, и игрок берёт их все. Либо в двух их поровну, и игрок опять же берёт их все. Это клетки в том же столбце, что и (0,0), в той же строке, и клетки на той же диагонали.
— Так это же та же самая задача про ходы ферзём! — вдруг осенило Мику. — Когда мы берём фишки из первой кучи, мы переходим в клетку в той же строке. Когда берём фишки из второй кучи — в клетку в том же столбце. А когда берём поровну из обеих — ходим по диагонали. Только доска не 8×8, а бесконечная, и ферзь исходно может стоять где угодно.
— Красиво ты это подметил, — обрадовалась Женя.
— Но доска бесконечная, — тут же пригорюнился Мика, — как на такой доске можно что-то решать?
— А давай экспериментировать! Возьмём доску побольше и отметим, какие поля проигрышные, а какие выигрышные. Посмотрим, что получится!
(Попробуйте самостоятельно сделать то же самое и сформулировать свои наблюдения — а может, и доказать их!)
Через десять минут, сверив результаты и исправив ошибки, Мика и Женя смотрели на картинку (рис. 3).
Рис. 3. Цзяньшицзы: найденные Микой и Женей выигрышные и проигрышные позиции
— Проигрышные поля явно образуют две симметричные цепочки, выше и ниже диагонали, — начал Мика. — А область между ними заполнена диагоналями из выигрышных позиций. И диагонали идут подряд: вот сверху каждая новая проигрышная позиция лежит ровно над диагональю, стартовавшей из предыдущей.
— Что цепочки симметричны, это понятно: задача же симметрична, — продолжила Женя. — А что диагонали последовательны — это ты хорошо заметил. Но у нас рисунок уже совсем исчёрканный — давай его перерисуем, оставив только проигрышные позиции и диагонали, может быть, ещё что-то заметим?
(Попробуйте сделать то же самое и сформулировать: не получается ли заметить ещё что-нибудь?)
Когда рисунок был перерисован, Женю озарило:
— Ну конечно, теперь это бросается в глаза! Давай проведём ломаную, соединив отрезками последовательные проигрышные позиции в верхней цепочке.
Тогда там будут отрезки только двух видов!
— И правда, — проведя эти отрезки, согласился Мика. — Короткие отрезки — это если следующее проигрышное поле отличается на 1 клетку по горизонтали и на 2 по вертикали. А длинные соответствуют сдвигу на 2 клетки по горизонтали и на 3 по вертикали. Чтобы лучше было видно, проведём их разными цветами — короткие отрезки синим, а длинные красным.
— А ещё, — подхватила Женя, — над проигрышной позицией только выигрышные. Давай нарисуем пожирнее линии выигрышных позиций, идущие из проигрышных позиций нижней цепочки. Смотри, красные отрезки их «перепрыгивают», а синие — нет (рис. 4)!
Рис. 4. Цзяньшицзы: Женя и Мика раскрашивают проигрышные позиции
— А всё-таки, как доказать, что диагонали появляются последовательно? — задумался Мика.
Рис. 5. Анализ столбцов
— Давай это сначала переформулируем, — предложила Женя. — Возьмём какой-то один столбец и отметим большими красными точками клетки, где начинается или проходит какая-то диагональ от проигрышной позиции. Если диагонали появляются последовательно, красные точки должны идти сплошной группой (рис. 5а).
— Не знаешь, как доказывать, доказывай по индукции, — сделав нарочито-важный вид, спародировал учителя Мика. — Давай посмотрим, что тогда будет в следующем столбце!
— Давай! — поддержала Женя. — Все выигрышные клетки, откуда можно было выигрывать ходом по диагонали, в новом столбце сдвинуты относительно старого на одну клетку вверх. Так что они опять образуют плотную группу. Вопрос только в том, почему новая проигрышная клетка будет с ней соседней?
— Смотри, — продолжил Мика, — если из какой-то клетки в левом столбце можно было выиграть ходом по горизонтали, то из такой же клетки в правом столбце тоже можно выиграть ходом по горизонтали. Так что в правом столбце ниже сдвинувшейся группы проигрышной может оказаться только соседняя с ней снизу клетка — все остальные точно выигрышные, из них можно выиграть ходом по горизонтали (рис. 5в).
— А если эта клетка не будет проигрышной, — подхватила Женя и дорисовала ещё один столбец (рис. 5г), — тогда проигрышной будет клетка сразу за сдвинутой группой. Потому что диагональным ходом из неё выиграть нельзя; вертикальным тоже — ниже проигрышной нет. А если бы можно было выиграть горизонтальным, сходив в какую-нибудь проигрышную клетку левее, то диагональ из этой проигрышной клетки в нашем столбце пришла в какую-то красную клетку ещё выше (рис. 5б). А мы взяли клетку выше всей красной группы. В обоих случаях проигрышная клетка в новом столбце оказывается соседней с теми клетками, где можно выиграть диагональным ходом — так что красная группа опять получается сплошной.
— То есть это мы доказали? — обрадовался Мика.
Рис. 6. Связь между цепочками
— Ага, — согласилась Женя. — А ещё смотри, что я придумала: начинающиеся в клетках нижней цепочки столбцы нарезают доску на полоски. Но в нижней цепочке проигрышных клеток тоже есть длинные и короткие отрезки — так что у нас получаются широкие и узкие полоски. Давай посмотрим на отрезки, правые концы которых попадают в какуюнибудь из этих полос.
Она взяла чистый лист и перерисовала по отдельности нужные места из таблицы на рисунке 4: получился рисунок 6.
В узкой полосе, в полосе над коротким отрезком, будет заканчиваться только длинный отрезок, — сказала она, показывая на рисунок 6, слева.
— Точно; а в полосе над длинным отрезком всегда заканчивается один длинный и один короткий, — подхватил Мика, смотря на рисунок 6, справа.
— Именно. Но цепочки-то симметричные! — продолжила Женя. — Значит, зная небольшую начальную часть верхней цепочки, её можно отразить и построить над ней более длинную часть верхней.
— А давай пойдём вдоль верхней цепочки, начиная с клетки (1,2), и будем писать букву «A», встречая длинный отрезок, и «B», встречая короткий, — предложил Мика. — Получится бесконечное слово, и ты говоришь, что если в нём каждую букву A заменить на AB, а каждую B на A, то оно останется самим собой?
— Ага, именно так, — подтвердила Женя. — Смотри, вот у нас получается такое слово:
ABAABABA...
— Когда мы сделаем замену, — продолжила она, — получится то же самое слово. Вот смотри:
AB A AB AB A AB A AB ...
— Точно. Но мы же это слово и машину, делающую эту замену, уже у Квантика видели! — вспомнил Мика.
И правда видели — но это уже совсем другая история... (См. комментарий.)
Комментарий. Со словами на ленте, сохраняющимися при таких заменах, наши герои встречались в статье «Слова на ленте» в «Квантиках» №5 и №6 за 2020 год. Получающееся в этой игре слово называется словом Фибоначчи.
Рассказ про те же игры с другой точки зрения — с числами Фибоначчи и золотым сечением \( \phi =\frac{\sqrt[]{5}+1}{2}\) читайте в «Кванте» №7 за 1984 год: А. Матулис, А. Савукинас «Ферзя — в угол, «цзяньшицзы» и числа Фибоначчи».
Как оказывается, проигрышные клетки верхней цепочки можно найти так: их координаты — это последовательность целых частей
\(x_{n}=[\phi n],y_{n}=[\phi ^{2} n]=[(\phi +1)n]\).
Анализ этой же игры имеется в статье, вышедшей в 1936 году в 8 выпуске первой серии «Математического просвещения»: И. В. Арнольд «Об одном свойстве числа \(\tau=\frac{\sqrt[]{5}+1}{2}\)».
Художник Мария Усеинова
1 Генкин С. А., Итенберг И. В., Фомин Д. В. Ленинградские математические кружки (МЦНМО, 2023). Наши герои её решают в развёрнутом на 180° варианте. См. также на сайте problems.ru задачу 30462.
Рис. 1. Задача о ферзе: первые шаги