В школьные годы (1990) в одном из детских журналов мне встретилось описание незамысловатой математической игры. Суть её такова.
Задаётся некое натуральное число. Двое играющих по очереди производят с числом арифметические действия: если число чётное, то его делят пополам, если нечётное — то умножают на 3 и по своему усмотрению прибавляют или отнимают 1. Побеждает тот, кто своим действием получает единицу.
Конечно же, существует и обратная игра, когда тот, кто получает единицу, проигрывает.
Так как мне всегда было интересно возиться с числами, то возник вопрос выигрышной стратегии. Игра ведь очень проста — выбор имеется, если в твой ход тебе досталось нечётное число, как выбрать, отнимать или прибавлять единицу от его произведения на 3, чтобы выиграть?
Решение появилось, когда в том же году из книги Жака Арсака я узнал о функции Шпрага-Гранди (в книге фамилии математиков Sprague и Grundy переводчики передали неправильно: Спраг и Грюнди). Суть такова: каждой игровой позиции присваивается число, 0 — если позиция проигрышна для игрока, чья очередь делать ход; все остальные числа, естественно, означают выигрышную позицию. Вычисляются эти числа так: нужно найти все позиции, достижимые из текущей, и взять минимальное целое неотрицательное число, не найденное среди значений Шпрага-Гранди для этих позиций.
Пример для нашей игры.
SG(1) = 0, так как если мы получаем единицу, то выигрываем
SG(2) = 1, так как из двойки мы можем получить только 1, а SG(1) = 0
SG(4) = 0, так как из четвёрки мы получим только 2, а SG(2) = 1
SG(8) = 1 по тем же соображениям
Для степеней двойки всё просто.
Чему же равно SG(3)? Из тройки можно получить 3×3−1=8 и 3×3+1=10. SG(8) = 1, а SG(10) получить не так легко, но после некоторых вычислений можно узнать, что SG(10) = 0. Минимальное целое число, не равное 1 и 0 — это 2. То есть SG(3) = 2.
Для обратной игры всё немного не так: SG´(1) = 1, SG´(2) = 0, SG´(4) = 1, а вот SG´(3) = 1, так как SG´(8) = 0 и SG´(10) = 0.
Написав программу, можно вычислить числа Шпрага-Гранди для обоих вариантов игры вплоть до некоторого значения. Зная эти числа, можно легко одержать победу.
Пример:
Даётся число 7.
Мой ход. Из 7 можно получить 20 и 22. SG(20) = 1, SG(22) = 0, так что я выбираю 22.
Противник делит результат пополам: 22÷2=11. SG(11) = 2.
Я: 11×3+1=34. Если бы я выбрал вычитание, то получилось бы 32, степень двойки, которая быстро привела бы к моему проигрышу, так как SG(32) = 1. SG(34) = 0.
Противник: 34÷2=17. SG(17) = 2.
Я: Из 17 можно получить 50 и 52. SG(50) = 0, SG(52) = 1, поэтому выбирать не приходится: 17×3−1=50.
Противник: 50÷2=25. SG(25) = 2.
И так далее. Если я не сделаю ошибки, противник никогда своим ходом не сможет получить позиции с числом Шпрага-Гранди, равным нулю!
И напоследок интересное наблюдение. Казалось бы, числа Шпрага-Гранди для прямой и обратной игры для одних и тех же позиций должны сильно различаться. Однако, посмотрев на таблицу значений SG для обоих вариантов, мы увидим, что они отличаются весьма мало! Многие позиции являются выигрышными (или, наоборот, проигрышными) для обоих вариантов игры. Так, SG(n) = SG´(n) = 0 для n = { 6, 10, 10, 14, …} и SG(n) = SG´(n) = 1 для n = { 12, 13, 19, 20, …}. Чем n больше, тем больше и совпадений. К примеру, SG(2731) = 2 для обычной игры и SG´(4096) = 1 для обратной, SG(4096) = 0 и SG´(4096) = 1, значения же чисел Шпрага-Гранди для n от 2732 и 4095 совпадают для обеих игр: SG(n) = SG´(n) для n = [2731, 4095].
На этом, пожалуй, всё.
Задача. Найдите числа Шпрага-Гранди для прямой и обратной игры для n от 1 до 4096.
Декабрь 2016 г.