стратегия - Игра в квадраты

Игра полностью исследуется при помощи функции Гранди. Через $%m\oplus n$% я буду обозначать поразрядную двоичную сумму чисел $%m$% и $%n$%, где в каждом разряде происходит сложение по модулю 2.

Пусть $%I_n$% -- игра для доски $%2\times n$%, где $%n\ge0$%. Через $%G(n)$% обозначаем функцию Гранди для этой игры. При этом $%G(0)=0$% (ходов нет; начинающий в данной позиции проиграл) и $%G(1)=0$% (первый ход всегда ведёт к позиции, выигранной для того, кто в ней начинает). Укажем рекуррентную процедуру для вычисления $%G(n)$%. Проигранные для начинающего позиции соответствуют нулевому значению этой функции.

Если первым ходом удаляется квадрат $%2\times2$%, то далее возникают две независимых игры $%I_k$% и $%I_{n-k-2}$%, то есть прямая сумма игр $%I_k\oplus I_{n-k-2}$%. Значение функции Гранди для такой игры равно $%G(k)\oplus G(n-2-k)$%, и все эти числа нам известны. Если первым ходом удаляется одна клетка из $%(k+1)$%-го столбца, то возникает прямая сумма игр вида $%I_k\oplus I_{n-1-k}\oplus J$%, где $%J$% есть тривиальная игра на доске из одной клетки, заканчивающаяся в один ход. Функция Гранди при этом равна $%1$%. Для прямой суммы трёх игр значение функции Гранди равно $%G(k)\oplus G(n-1-k)\oplus1$%. Эти числа мы также знаем.

Теперь для объединения двух описанных выше множеств чисел мы рассматриваем наименьшее целое неотрицательное число, не принадлежащее объединению. Это и будет число $%G(n)$%.

Несложно реализовать описанный алгоритм в виде программы. Вычисление при помощи Maple привели к такой последовательности чисел $%G(n)$% для $%0\le n < 120$%:

0, 0, 2, 2, 1, 4, 3, 3, 1, 4, 2, 6,

5, 0, 2, 7, 1, 4, 3, 3, 1, 4, 7, 7,

5, 0, 2, 8, 4, 4, 6, 3, 1, 8, 7, 7,

5, 0, 2, 2, 1, 4, 6, 3, 1, 8, 2, 7,

5, 0, 2, 8, 1, 4, 6, 3, 1, 4, 2, 7,

5, 0, 2, 8, 1, 4, 6, 3, 1, 8, 7, 7,

5, 0, 2, 8, 1, 4, 6, 3, 1, 8, 2, 7,

5, 0, 2, 8, 1, 4, 6, 3, 1, 8, 2, 7,

5, 0, 2, 8, 1, 4, 6, 3, 1, 8, 2, 7,

5, 0, 2, 8, 1, 4, 6, 3, 1, 8, 2, 7, ...

Легко видеть, что нули стоят в точности на местах с номерами вида $%n\equiv1\pmod{12}$% (вырожденный случай $%n=0$% не считается). Последовательность имеет почти периодическую структуру с периодом длиной 12. Здесь требуется обоснование, почему периодичность будет наблюдаться, начиная с некоторого момента. Я это обоснование опускаю, но его при желании можно рассмотреть.