Для раскрытия темы, разберем вариацию известной игры Ним.
И так, на столе лежат несколько кучек камней. за один ход разрешается либо взять произвольное число камней из любой кучки, любо разделить любую кучку на две непустых.
В обычных правилах игрок, который не может сделать ход, проигрывает. В поддавках же проигрывает тот, после чьего хода не останется камней на столе.
Решение
Для решения поставленой задачи, олимпиец должен быть знаком с Теорией игр
Анализ даной вариации игры не намного сложнее обычной игры.
Функция Шпрага-Гранди (или Спрага-Грюнди, как кто привык) для обычной игры имеет следующий вид.
G(n) =
{n-1 при n (mod 4) == 0},
{n при n (mod 4)==1 или 2},
{n+1 при n (mod 4)==3}
Доказательство можно привести индукцией по n. Случай n=1 тривиален (всегда можно всю кучку забрать и выиграть). Пусть наша функция Гранди справедлива для всех k<n. Проверим для n.
Вернемся к игре по измененным правилам.
Докажем утверждение, что игра аналогичная обычной, кроме случаев, когда во всех кучках по 1 камню. В таком случае от игроков ничего не зависит и результат игры определяется четностью n.
Доказательство.
Обозначим описанное множество позиций через P. Согласно определению чисел Шпрага Гранди покажем, что все позиции из P проигрышные, а все из !P (обозначение «не Р») выигрышные, и что из позиций из Р нет ходов в другие позиции из Р.
Легко доказать, что из любой позиции! Р существует ход в Р. Для этого надо немножко изменить стратегию игры. Скажем, если выбраным ходом мы оставляем 1 камень в кучке, вместо этого заберем всю кучку и наоборот, если мы забираем всю кучку, то вместо этого оставим 1 камень. И, наконец, если мы делим кучку на 2 по 1 камню мы всегда можем оставить только 1 камень.
Данный метод позволяет решать задачи с правилами «поддавки», рассмотрев только некоторые крайние случаи.
И так, на столе лежат несколько кучек камней. за один ход разрешается либо взять произвольное число камней из любой кучки, любо разделить любую кучку на две непустых.
В обычных правилах игрок, который не может сделать ход, проигрывает. В поддавках же проигрывает тот, после чьего хода не останется камней на столе.
Решение
Для решения поставленой задачи, олимпиец должен быть знаком с Теорией игр
Анализ даной вариации игры не намного сложнее обычной игры.
Функция Шпрага-Гранди (или Спрага-Грюнди, как кто привык) для обычной игры имеет следующий вид.
G(n) =
{n-1 при n (mod 4) == 0},
{n при n (mod 4)==1 или 2},
{n+1 при n (mod 4)==3}
Доказательство можно привести индукцией по n. Случай n=1 тривиален (всегда можно всю кучку забрать и выиграть). Пусть наша функция Гранди справедлива для всех k<n. Проверим для n.
- Из такой кучки можно получить кучку любого меньшего размера удалением необходимого числа камней, тоесть нашу функцию с меньшим параметром.
- Можно убедиться, что разделение кучки на две не позволяет получить позицию с числом Гранди, отличным от G(k), k<n, кроме n=4*k+3. Тогда, P(1, n-1) = G(1) xor G(n-1) = 1 xor (4*k+2) = 4*k+3 = n. Тоесть, G(4*k+3) = n+1.
Вернемся к игре по измененным правилам.
Докажем утверждение, что игра аналогичная обычной, кроме случаев, когда во всех кучках по 1 камню. В таком случае от игроков ничего не зависит и результат игры определяется четностью n.
Доказательство.
Обозначим описанное множество позиций через P. Согласно определению чисел Шпрага Гранди покажем, что все позиции из P проигрышные, а все из !P (обозначение «не Р») выигрышные, и что из позиций из Р нет ходов в другие позиции из Р.
Легко доказать, что из любой позиции! Р существует ход в Р. Для этого надо немножко изменить стратегию игры. Скажем, если выбраным ходом мы оставляем 1 камень в кучке, вместо этого заберем всю кучку и наоборот, если мы забираем всю кучку, то вместо этого оставим 1 камень. И, наконец, если мы делим кучку на 2 по 1 камню мы всегда можем оставить только 1 камень.
Данный метод позволяет решать задачи с правилами «поддавки», рассмотрев только некоторые крайние случаи.
