Чтобы расширить тему, давайте рассмотрим вариант знаменитой игры Ним.
И вот, на столе лежит несколько кучек камней.
за один ход разрешается либо взять произвольное количество камней из любой кучки, либо разделить любую кучку на две непустые.
В обычных правилах проигрывает игрок, который не может сделать ход. В раздачах проигрывает тот, после хода которого на столе не осталось камней.
Решение Для решения задачи олимпиец должен знать Теория игры Анализ этого варианта игры не намного сложнее обычной игры.
Функция Спрага-Гранди (или Спрага-Гранди, как кто привык) для обычной игры имеет следующий вид. Г(п) = { n-1 для n (mod 4) == 0}, { н для n (mod 4)==1 или 2}, { п+1 для n (мод 4)==3} Доказательство может быть задана индукцией по n. Случай n=1 тривиален (вы всегда можете забрать всю стопку и выиграть).
Пусть наша функция Гранди справедлива для всех k Из такой кучи можно получить кучу любого меньшего размера, удалив необходимое количество камней, то есть нашу функцию с меньшим параметром.
Можно убедиться, что разделение кучи на две не позволит получить позицию с числом Гранди, отличным от G(k), k Вернемся к игре по измененным правилам.
Докажем утверждение, что игра аналогична обычной, за исключением случаев, когда во всех стопках по 1 камню.
В этом случае от игроков ничего не зависит и результат игры определяется четностью n. Доказательство.
Обозначим описанное множество позиций через P. Согласно определению чисел Шпрага-Грунди покажем, что все позиции из P проигрышные, и все позиции из !P (обозначение «не P») выигрышные, а из позиции из P нет ходов на другие позиции из P. Это легко доказать с любой позиции! В П есть ход. Для этого нужно немного изменить стратегию игры.
Допустим, если выбранным ходом мы оставим в кучке 1 камень, вместо него мы возьмем всю стопку, и наоборот, если мы возьмем всю стопку, вместо нее оставим 1 камень.
И, наконец, если мы разделим кучу на 2 камня по 1, то всегда сможем оставить только 1 камень.
Этот метод позволяет решать проблемы с правилами раздачи, рассматривая лишь некоторые крайние случаи.
Теги: #теория игр #Шкаф #гранди #раздача.
-
Почему Erp Для Бизнеса?
19 Oct, 24 -
Маленький, Маленький Юбилей
19 Oct, 24 -
Синтетическая Телепатия
19 Oct, 24 -
Радиожурналисты Создали Pod-Станцию
19 Oct, 24 -
Yahoo Задерживает Панаму
19 Oct, 24
