Модификация игры Ним

[OwnYou]

Я рассмотрел Гранди-функцию для этой игры и так получается что она имеет значения только 0 и 1 на любых наборах т.е. заранее известно какой игрок выигрывает... вообще не понимаю как такое может быть... я туплю наверное... подскажите пожалуйста

Ну а что ты ожидал увидеть?

В детерминированных (без случайностей) играх, когда каждый игрок обладает полной информацией о состоянии игры на каждом ходу (в противоположность, например, картам, где нельзя видеть карты другого игрока), игра всегда заканчивается победой одного определенного игрока (или ничьей, если игра допускает ее), если оба игрока играют безупречно.

Например, шашки - одна из таких игр. И недавно выяснилось что при оптимальной игре обоих сторон будет ничья.

[OwnYou]

всё правильно, здесь Take-And-Brake игра, которая заканчивается победой одного игрока... НО, я не об этом.
По условию игры: (1) - это терминальная позиция следовательно Гранди функция G(1)=0 по определению. Гранди функция всех позиций ведущих в терминальную = 1 т.е. G(2)=1. Дальше рекурсивно вычисляем G по правилу:
G(n) = mex{G(n-1,1), G(n-2,2), ... , G(1,n-1)}
а сумма игр т.е. G(X1,X2,..,Xn)=G(X1) xor G(X2) xor ... xor G(Xn) по теореме Sprague-Grandy.
и получается такая штука, что G(2n-1)=0 , а G(2n)=1 при любом натуральном n.
у меня напрашивается из этого такое предположение, что я не могу повлиять на ход игры... т.е. заранее знаю кто выиграет или проиграет.

к примеру если добавить ещё одну терминальную позицию, например (2) то такой ситуации уже не будет и можно влиять на ход игры. Что с этой игрой не так... HELP... где ошибся или всё так?????

G(X1,...,Xn)=0 Это P-позиция, в которой выигрывает игрок сделавший предыдущий ход
G(X1,...,Xn)!=0 Это N-позиция , в которой выигрывает игрок делающий следующий ход

т.е. если мы будем находиться в P-позиции, надо сделать ход снова в P-позицию.
рассмотрим игру (9,8,6) которая будет достаточно большой. G(9,8,6)= 0 xor 1 xor 1 = 0 --> это P-позиция(проигрышная)

G(9,8,6) ходим в первой куче:

G(8,1,8,6) = 1 xor 0 xor 1 xor 1 = 1
G(7,2,8,6) = 0 xor 1 xor 1 xor 1 = 1
G(6,3,8,6) = 1 xor 0 xor 1 xor 1 = 1
G(5,4,8,6) = 0 xor 1 xor 1 xor 1 = 1

G(9,8,6) ходим во второй куче:

G(9,1,7,6) = 0 xor 0 xor 0 xor 1 = 1
G(9,2,6,6) = 0 xor 1 xor 1 xor 1 = 1
G(9,3,5,6) = 0 xor 0 xor 0 xor 1 = 1
G(9,4,4,6) = 0 xor 1 xor 1 xor 1 = 1

G(9,8,6) ходим в третей куче:

G(9,8,1,5) = 0 xor 1 xor 0 xor 0 = 1
G(9,8,2,4) = 0 xor 1 xor 1 xor 1 = 1
G(9,8,3,3) = 0 xor 1 xor 0 xor 0 = 1

Никак нельзя сделать ход в P-позицию.... тут наверно даже доказать можно...

Я немного подумал, и нашел более элементарное объяснение: ваша игра всегда заканчивается за (a-1) + (b-1) + (c-1) ходов, независимо от действий игрока.

Представьте себе что кучки - это полоски бумаги состоящие из n клеточек в ряд, и за один ход разрешается разрезать на две любую из имеющихся бумажек, на длине от края кратной длине клеточки. Очевидно в игре изначально можно сделать a-1 + b-1 + c-1 разрезов, и игра закончится только в момент когда все эти разрезы будут сделаны, а порядок их неважен. (Более формальное доказательство - рассмотреть величину сумма (размер кучки - 1) по всем кучкам, и доказать что она уменьшается на 1 за каждый шаг)

[OwnYou]

Спасибо! вот теперь я на 99% уверен. пойду теперь на препода наезжать =)

[Templar]

Это и есть классическая игра "Ним";