Имеется шахматная доска $%2 \times n$%. Два игроки поочередно вырезают и забирают из нее квадраты $%1 \times 1$% и $%2 \times 2$%. Распилы можно делать вдоль границ клеток шахматной доски. Выиграет тот, кто заберет последний квадрат. Верно ли, что первый игрок может выиграть при всех $%n \ne 1\left( {\bmod 12} \right)$%?

(Решения не знаю).

задан 24 Ноя '14 20:35

изменен 24 Ноя '14 20:53

1

Я сейчас осознал, что эта задача точно должна просчитываться до конца. Но там надо немного посчитать: ответ сразу не виден. К вечеру (ближе к ночи) постараюсь это всё сделать. Очень интересно, что получится в итоге.

(25 Ноя '14 17:55) falcao
10|600 символов нужно символов осталось
3

Игра полностью исследуется при помощи функции Гранди. Через $%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

1

@falcao, я тоже делал попытки, для конкретных случаев алгоритмы строились, но не получил рекурсии в каком-либо виде, допускающем обобщение на случай произвольного n. Специально дожидался Вашего результата. Очень красиво – нет слов!

(26 Ноя '14 3:08) Urt
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×33

задан
24 Ноя '14 20:35

показан
7270 раз

обновлен
26 Ноя '14 3:08

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru