Имеется шахматная доска $%2 \times n$%. Два игроки поочередно вырезают и забирают из нее квадраты $%1 \times 1$% и $%2 \times 2$%. Распилы можно делать вдоль границ клеток шахматной доски. Выиграет тот, кто заберет последний квадрат. Верно ли, что первый игрок может выиграть при всех $%n \ne 1\left( {\bmod 12} \right)$%? (Решения не знаю). задан 24 Ноя '14 20:35 EdwardTurJ |
Игра полностью исследуется при помощи функции Гранди. Через $%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. Здесь требуется обоснование, почему периодичность будет наблюдаться, начиная с некоторого момента. Я это обоснование опускаю, но его при желании можно рассмотреть. отвечен 26 Ноя '14 2:40 falcao |
Я сейчас осознал, что эта задача точно должна просчитываться до конца. Но там надо немного посчитать: ответ сразу не виден. К вечеру (ближе к ночи) постараюсь это всё сделать. Очень интересно, что получится в итоге.