Занятие 14

В беспристрастных играх можно применить специальные методы, позволяющие быстро определить, является ли позиция выигрышной или проигрышной для участника, делающего первый ход. Игра ним – это игра двух игроков, основанная на поочередном взятии камешков из одной или нескольких кучек. Ограничения на количество изымаемых из кучки камней могут быть различны. Рассмотрим сначала несколько вариантов игры с одной кучкой.

Пусть из кучки можно брать от 1 до `k` камней и первоначально в кучке `n` камней. Выигрывает тот, кто берет последний камень. Если в кучке от 1 до `k`, выигрывает первый игрок. Если в кучке `k+1` камень, то любой ход первого игрока приводит к ситуации, выигрышной для второго игрока. Для кучки от `k+2` до `2*k+1` у первого игрока есть ход, после которого в кучке остается `k+1` камень. Анализируя дальше, можно сделать вывод, что проигрышными являются кучки с числом камней кратным `k+1`. Результаты анализа удобно представить в таблице, в которой плюсом отмечены позиции выигрышные для первого игрока, а минусом — проигрышные. Пример таблицы для `k=3`.

Проигрышными являются те позиции, любой ход из которых приводит к выигрышной позиции. Заполнение таблицы результатов выполняется как в задачах динамического программирования, и этот способ можно использовать для решения задачи в общем случае. Мизерный вариант игры получается сдвигом результатов исходной игры на одну клетку.

То есть проигрышными становятся кучки, в которых число камней `n` mod `(k+1)\ =\ 1`.

Рассмотрим следующую игру. За ход из кучки разрешается брать любое число камней являющееся степенью числа 2 (то есть 1, 2, 4, 8 и т.д.). Построим таблицу. Если в кучке 1 или 2 камня, то выигрывает первый игрок. Если 3 камня, то первый проигрывает. Для 4 и 5 камней опять выигрывает первый, оставляя второму кучку из 3 камней.

Анализ таблицы позволяет сделать предположение, что проигрышными позициями для первого игрока будут кучки из `3*m` камней, так как в них не существует хода, с помощью которого он может получить проигрышную позицию. Не существует целого p такого, что `(3*m\ -\ 2^p)\ ` mod 3 = 0, так как `(3*m)\ ` mod 3 = 0, а `2^p` mod 3 `≠\ 0.`

Если можно брать от 1 до `[n/2]` камней, то проигрышными будут позиции с числом камней 2, 5, 11, 23, 47, …, `3*(2^p-1)+2`.