Где спрятался Ним?

МАТЕМАТИ Ч ЕСКИ Й КРУ Ж ОК

Где спрятался Ним?

И.КОПЫЛОВ

ВСТАТЬЕ «ПЛЮСЫ–МИНУСЫ И ИГРА НИМ»

(см. «Квант» №7, 8 за 2018 г.) была рассказана стратегия игры Ним, которая играет особую роль в теории игр. Игра Ним состоит в следующем. Имеется m кучек, количество камней в которых равно $a_{1}, a_{2}$, … $, a_{m}$. Двое ходят по очереди; каждый игрок при своем ходе выбирает одну из кучек и берет из нее любое ненулевое число камней. Побеждает тот, кто забрал последний камень. Многие игры сводятся к Ниму. Если в игре удается распознать Ним, то для нее сразу же появляется стратегия, заимствованная из Нима. В данной статье сведем к Ниму несколько разнообразных игр. Игра 1. Пять фишек находятся на клетках горизонтальной полоски из 25 клеток. За каждый ход необходимо передвинуть одну из фишек влево на любую клетку, перепрыгивать через другие фишки разрешается, на одной клетке могут находиться несколько фишек. Выигрывает игрок, после хода которого все 5 фишек окажутся на крайней левой клетке полоски. Игра очевидным образом сводится к Ниму с 5 кучками камней. Занумеруем клетки полоски, начиная с 0, слева направо (рис.1). Тогда фишку, стоящую на клетке с номером n, за 1 ход можно передвинуть на любую из клеток 0, 1, …, n 1 вне зависимости от расположения остальных фишек. Аналогично и в игре Ним количество камней в одной из кучек за ход уменьшается вплоть до 0. Поэтому для сведения к Ниму фишку на клетке n следует заменить кучкой с n камнями. Тогда фишка на самой левой клетке

равносильна пустой кучке. Игра заканчивается, когда все кучки пусты, т.е. все фишки собраны на клетке с номером 0. Итак, если 5 фишек расположены на клетках с номерами a, b, c, d и e, то для чисел a, b, c, d и e составляется Ним-сумма. Напомним, что Ним-сумма вычисляется поразрядно следующим образом: Ним-суммируемые числа записываются в двоичной системе исчисления, и если в данном разряде оказалось нечетное число единиц, то в результирующей сумме в соответствующем разряде ставим 1, если четное – 0. Ним-сумма чисел а, b, с, d, е обозначается a † b † c † d † e. Своим ходом игрок должен обнулить Нимсумму. Рассмотрим пример. Пусть фишки стоят на клетках 5, 10, 14, 16 и 22 полоски (см. рис.1). Вычисление соответствующей Нимсуммы приведено на рисунке 2.

Рис. 2. Вычисление Ним-суммы для определения хода в игре 1

Итак,

5 † 10 † 14 † 16 † 22

$= 101_{2}$ † $1010_{2}$ † $1110_{2}$ † $10000_{2}$ † $10110_{2} 111_{2} 7$.

Ним-сумма отлична от 0. Игрок, делающий ход, должен ее обнулить. Старшая единица в Ним-сумме находится во 2-м двоичном разряде, если считать разряды справа налево, начиная с нулевого. Единицы во втором разряде присутствуют в записи количеств камней в 1, 3 и 5 кучках. Поэтому в рассматриваемом примере у игрока есть 3 варианта хода: либо в первой кучке оставить $10_{2} 2$ камня, т. е. передвинуть фишку с

Рис. 1. Нумерация клеток полоски и расположение фишек в примере

DOI: https://doi.org/10.4213/kvant20190405

(Продолжение см. на с. 34)

34

КВАНТ 2019/№4

клетки 5 на клетку 2, либо в третьей кучке оставить $1001_{2} 9$ камней, т. е. передвинуть фишку с клетки 14 на клетку 9, либо в пятой кучке оставить $10001_{2} 17$ камней, что означает перестановку фишки с клетки 22 на клетку $17. Игра^{2.}$ Гусеница состоит из 20 звеньев. Некоторые звенья гусеницы окрашены в зеленый цвет, остальные – белые. Два игрока по очереди перекрашивают звенья: зеленое звено делают белым, а белое – зеленым. Своим ходом игрок должен перекрасить одно из зеленых звеньев в белый цвет и может перекрасить еще одно звено, расположенное ближе к хвосту относительно перекрашенного. Выигрывает игрок, после хода которого все звенья гусеницы станут белыми. Данная игра представляет собой скрытый Ним. Пронумеруем звенья гусеницы, начиная с хвоста. Хвостовое звено получит номер 1, головное – 20 (рис.3). Зеленое звено

Рис. 4. Вычисление Ним-суммы для определения хода в игре 2

с 7 кучками с 2, 5, 6, 9, 14, 16 и 19 камнями. Так как соответствующая Ним-сумма равна (рис.4)

2 † 5 † 6 † 9 † 14 † 16 † 19

$= 10_{2}$ † $101_{2}$ † $110_{2}$ † $1001_{2}$ † $1110_{2}$ †

$10000_{2}$ † $10011_{2}$ †

101 2

5 и есть кучка с 5 камнями, то игроку, делаю-

Рис. 3. Нумерация звеньев гусеницы

гусеницы с номером k заменим кучкой с k камнями. Игрок при своем ходе перекрашивает зеленое звено с некоторым номером k и может перекрасить еще одно звено с номером, меньшим k. Если игрок перекрашивает только одно звено, то считаем, что он опустошил кучку с k камнями. Если второе перекрашенное звено имеет номер m (m < k) и до хода игрока было белым, то считаем, что игрок из кучки с k камнями забрал k – m камней и оставил в ней m камней. А в том случае, когда второе перекрашенное звено с номером m было зеленым, а стало белым, то будем считать, что игрок в кучке с k камнями оставил m камней. Так как до этого уже была кучка с m камнями, то их стало уже две. А две одинаковые кучки вклад в Ним-сумму дают нулевой. Поэтому далее в игре Ним их можно не рассматривать и исключить из игры. Таким образом, данная игра сводится к Ниму с количеством кучек, равным количеству зеленых звеньев гусеницы. Количество камней в кучке совпадает с номером соответствующего зеленого звена. Например, на рисунке 3 игра с перекрашиванием звеньев гусеницы эквивалентна Ниму щему ход, достаточно обнулить кучку из 5 камней, и Ним-сумма оставшихся кучек станет равной 0. Следовательно, выигрышный ход из состояния на рисунке 3 – перекрасить зеленое звено 5 в белый цвет. $Игра^{3.}$ Два игрока по очереди разламывают плитку шоколада, разделенную бороздками на 8 u 12 частей. Одна из частичек плитки помечена крестом. Игрок при каждом своем ходе разламывает плитку вдоль одной из бороздок и съедает ту часть плитки, которая не содержит частички с крестом. Побеждает игрок, после хода которого от плитки шоколада остается всего лишь одна частичка с крестом. Эта игра – тоже завуалированный Ним. У игрока существует 4 варианта хода: разломить плитку по бороздке выше частички с крестом, правее частички с крестом, ниже ее либо левее ее. Если в начале игры частичка с крестом расположена, например, так, как показано на рисунке 5, то над частичкой с крестом расположено 4 ряда, правее ее – 5 рядов, ниже – 3 ряда, левее – 6 рядов. Ход в каждом из четырех вариантов уменьшает количество рядов соответствующего направления.

35

М АТ ЕМ АТИ Ч ЕС КИ Й

Рис. 5. Вид плитки шоколада с выделенной крестом частичкой

Поэтому игра эквивалентна Ниму с 4 кучками камней. В первой кучке количество камней совпадает, например, с количеством рядов над частичкой с крестом, во второй – с количеством рядов правее частички с крестом, в третьей – ниже и в четвертой – левее ее. В примере на рисунке 5 в начале игры в кучках находится 4, 5, 3 и 6 камней. Игрок при своем ходе выбирает кучку и уменьшает в ней количество камней. Для определения хода составляем Нимсумму. В рассматриваемом примере вычисление Ним-суммы проведено на рисунке 6. Получим 4 † 5 † 3 † $6 100_{2}$ † $101_{2}$ † $11_{2}$ † $110_{2}$

$100_{2} 4$. Как видно из рисунка 6, Ним-сумма отлична от 0. Для ее обнуления необходимо удалить

Рис. 6. Составление Ним-суммы для определения хода в игре 3

одну единицу в старшем двоичном разряде, т.е. удалить 4 камня в одной из кучек 1, 2 или 4. В рассматриваемой игре игрок должен удалить 4 ряда либо над, либо справа, либо слева от клетки с крестом. Игра 4. На пяти клетках горизонтальной полоски из 25 клеток находится по фишке. За каждый ход разрешается передвинуть любую фишку влево на свободную клетку, не перепрыгивая через другие фишки. Проигрывает игрок, который не может сделать ход. Занумеруем клетки полоски слева направо числами от 1 до 25. Фишки на полоске тоже будем нумеровать слева направо. Игрок не

КР У Ж ОК

может сделать ход, когда пять фишек занимают клетки с номерами от 1 до 5. Для поиска стратегии сначала упростим игру. Пусть на полоске находится всего одна фишка. Тогда выигрывает начинающий, поставив фишку на клетку 1. Если фишек на полоске две, то стратегия определяется без особых усилий. Игроку следует разместить фишки на соседних клетках. Соперник сможет сделать ход только фишкой 1. Игрок своим очередным ходом перемещает влево фишку 2 так, чтобы фишки опять оказались на соседних клетках. В итоге после нескольких ходов фишки окажутся на клетках 1 и 2, и соперник не сможет сделать ход. Далее рассмотрим случай игры с тремя фишками на полоске. Для построения стратегии воспользуемся правилами расстановки знаков «+» и «–», приведенными в статье «Плюсы–минусы и игра Ним». Состояние игры задают 3 числа – номера клеток с фишками. Поэтому расставлять знаки необходимо в клетках трехмерной таблицы. Координаты клеток $a_{1}, a_{2}, a_{3}$ удовлетворяют соотношениям

$0 a_{1} a_{2} a_{3}$,

(1) где $a_{1}$ – номер клетки с фишкой $1, a_{2}$ – с фишкой $2, a_{3}$ – с фишкой 3. В результате хода одного из игроков одна из трех координат уменьшается, причем соотношение (1) остается в силе. Заполнять знаками таблицу будем по слоям. В нижнем слое, где $a_{1} 1$, фишка 1 ходить не может. А для двух фишек мы уже установили, что в минусовом состоянии фишки размещаются в соседних клетках полоски. Значит, $a_{2} 1 a_{3}$, и во всех клетках с координатами $1, a_{2}, a_{2} 1, 1 a_{2}$, стоит знак «–», а во всех остальных клетках первого слоя – знак «+». В клетках второго слоя таблицы, где $a_{1} 2$, минусы находятся в клетках с координатами 2,3,5, 2,4,6, 2,5,7, …, т.е. в клетках вида $2, a_{2}, a_{2} 2, 2 a_{2}$. Заполняя знаками «+» и «–» клетки третьего слоя, замечаем, что минусы оказываются в клетках с координатами вида $3, a_{2}, a_{2} 3, 3 a_{2}$. Глядя на заполнение минусами первых трех слоев таблицы, можно предположить, что знаки «–» находятся в клетках с коорди-

36

КВАНТ 2019/№4

натами $a_{1}, a_{2}, a_{2} a_{1}, 0 a_{1} a_{2}$. Или, в другом виде, координаты $a_{1}, a_{2}, a_{3}$ минусовых клеток связаны соотношением a 1

$a_{3} a_{2}$.

(2)

Эта гипотеза доказывается методом математической индукции по $a_{1}$. Перепишем соотношение (2) в виде

$a_{1} 0$ a 3 a 2

(3) и предположим, что к полоске добавили слева еще одну клетку с номером 0, на которой стоит нулевая условная фишка. Тогда расстояние в клетках между первой и нулевой фишками совпадает с расстоянием в клетках между третьей и второй фишками. Если расстановка фишек удовлетворяет соотношению (3), то любой ход соперника

ряют соотношению

a 2 a 1

$a_{4} a_{3}$.

И, наконец, для 5 фишек на полоске введем опять условную неподвижную нулевую фишку, которую поместим на условную нулевую клетку, присоединенную к полоске слева. Игра сводится к Ниму с 3 кучками камней. Количество камней в первой кучке полагаем равным количеству свободных клеток между фишками 0 и 1. Размер второй кучки определяется количеством свободных клеток полоски между фишками 2 и 3. Камней в третьей кучке ровно столько, сколько свободных клеток полоски между 4-й и 5-й фишками. На рисунке 7 показан пример определения размеров трех кучек в эквивалентном Ниме.

Рис. 7. Пример определения количеств камней в игре 4

приведет к его нарушению, и игрок своим ответным ходом должен восстановить выполнение соотношения (3). Наблюдается соответствие Ниму с двумя кучками камней. Количество камней в первой кучке совпадает с количеством свободных клеток между нулевой и первой фишками, а во второй кучке – между второй и третьей фишками. В Ниме с двумя кучками игрок должен каждым своим ходом уравнивать количества камней в кучках. В отличие от Нима в данной игре соперник может, передвинув фишку 2, увеличить количество свободных клеток между фишками 2 и 3, что в игре Ним соответствует увеличению числа камней во второй кучке. В этом случае игрок должен ответным ходом передвинуть фишку 3 влево, вернув прежнее число свободных клеток между второй и третьей фишками. Случай с 3 фишками на полоске разобран. Пусть теперь игра проводится с 4 фишками на полоске. Тогда условная фишка, введенная при рассмотрении предыдущего случая, получает воплощение. Обозначим через $a_{i}$ номер клетки, на которой стоит i-я фишка (i = 1, 2, 3, 4). По аналогии с предыдущим случаем номера клеток с фишками для минусового состояния удовлетво-

В примере количества камней в кучках равны 4, 1 и 5. Для победы игрок должен каждым своим ходом обнулять соответствующую Ним-сумму для трех кучек. Перемещения фишек с нечетными номерами уменьшают количество камней в одной из кучек. Если соперник перемещает фишку 2 или 4, скажем, на k клеток влево, то в кучке 2 или 3 соответственно количество камней увеличивается. В этом случае игрок должен своим ходом восстановить количество камней в кучке, переместив соответствующую фишку с нечетным номером на k клеток влево. В рассматриваемом примере Ним-сумма равна 0 (рис.8). Следовательно, игрок, чья очередь делать ход, проигрывает.

Рис. 8. Вычисление Ним-суммы для 3 кучек в игре 4

Игра 5. Клетки полоски из 10 клеток пронумерованы от 1 до 10. На каждой

38

КВАНТ 2019/№4

Рис. 10. Составление Ним-суммы для чисел в игре 5

следует передвинуть из клетки 9 одну фишку, оставив на ней три фишки. Ним-сумма после такого хода станет нулевой. Игра 6. Игра происходит с 4 ломаными. Количество звеньев у ломаной не превышает 20. Три ломаные прикреплены к неподвижному основанию одним концом, а четвертая – обоими концами (рис. 11). За

Рис. 11. Пример начального состояния игры

каждый ход разрешается удалить одно звено у любой ломаной. Если после хода оказались звенья, оторванные от основания, то все они также удаляются. Выигрывает игрок, после хода которого звенья всех ломаных будут удалены. Сведем игру к Ниму с 4 кучками камней. Пусть ломаные А, В и С прикреплены к основанию одним концом, а ломаная D – двумя. Последовательно занумеруем звенья каждой ломаной. У ломаных А, В и С номер 1 получит звено, прикрепленное к основанию (рис.11). Покажем, что каждую из ломаных А, В и С можно заменить кучкой, количество камней в которой равно количеству звеньев в соответствующей ломаной. Пусть ломаная А, например, содержит k звеньев. При удалении i-го звена ломаной А, 1 d i d k, у нее остается i –1 звено с номерами от 1 до i –1. Тем самым, удаление i-го звена равносильно оставлению в кучке i –1 камня. Ломаную D также заменим на некоторую обобщенную кучку камней. Пусть ломаная

D вначале содержит m звеньев. После удаления одного из ее звеньев, скажем звена i, 1 d i d m, ломаная распадается на 2 ломаные с i –1 и m – i звеньями, каждая из которых прикреплена к основанию одним концом. Покажем, что 2 новые ломаные в игре можно заменить одной кучкой камней в Ниме. Если в ломаной D четное количество звеньев, то после удаления одного звена в полученных двух ломаных будет неравное количество звеньев, и у соперника есть возможность своим ходом уравнять количество звеньев в новых ломаных. Две одинаковые кучки имеют одинаковое двоичное представление и дают нулевой вклад в Нимсумму. Получаем, что и обобщенная кучка, которой мы хотим заменить ломаную D, дает нулевой вклад в Ним-сумму, т.е. является пустой. Отличие обобщенной кучки камней от простой при игре в Ним заключается в том, что даже когда обобщенная кучка является пустой, то возможен ход игрока, переводящий ее в непустую кучку. При этом соперник своим ходом обнуляет ее. И снова игрок должен делать ход, а обобщенная кучка – пуста. Вернулись к состоянию, которое уже было. После каждого хода суммарное количество звеньев у ломаных уменьшается, поэтому бесконечное количество раз возвращаться к одному и тому же состоянию обобщенной кучки невозможно. Рассмотрим теперь случай, когда у ломаной D нечетное количество звеньев. Тогда игрок удалением среднего звена может получить две ломаные с одинаковым числом звеньев, которые дают нулевой вклад в Нимсумму. Покажем, что при удалении любого другого звена ломаной D соперник может после своего последующего хода оставить две ломаные, вклад которых в Ним-сумму такой же, как и от кучки с одним камнем. Ломаная D после удаления одного звена не может распасться на две ломаные, количество звеньев в которых отличается ровно на 1. Но тогда соперник, уменьшая своим ходом количество звеньев у ломаной с большим числом звеньев, может получить в новых ломаных количества звеньев, являющиеся двумя последовательными числами, допустим 2n и 2n + 1, где наименьшее число 2n является четным. Вклад двух таких чисел в