$1$

Хотя это может показаться странным, чтобы показать элегантную математическую теорию, нужно вначале упростить задачу.

Элементарный ним

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

Естественно, землеройка первым же ходом берет и съедает все зерна из кучи, и бедному кроту ничего не остается как бежать в магазин за следующей порцией. Как Вы думаете сколько зерен должен принести крот, чтобы выиграть игру? Увы, единственный способ выиграть у крота — это схалтурить и не купить зерен вообще. Единственная проигрышная ситуация в игре — это если зерен вообще нет. Любая другая ситуация является выигрышной, так как можно забрать все зерна — таким образом перевести соперника в проигрышную ситуацию.

Что же делать кроту? Однажды он принес 6 зерен, но разделил их на 3 кучки размером 1, 2 и 3 зерна. Таким образом, крот предлагает сыграть в игру

Ним

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

Землеройка не почувствовала подвоха и съела все зерна из самой большой кучки из трех зерен. Перед кротом теперь две кучки с зернами — из одного зерна и двух зерен. Что он должен делать, чтобы выиграть?

Таким образом задача снова стала интересной и даже более нетривиальной, чем была вначале. Давайте попробуем проанализировать позиции, для начала используя понятия выигрышных и проигрышных позиций. Напомню, что позиция называется выигрышной, если у игрока есть алгоритм, состоящий из некоторого первого хода и способа ответа на всевозможные ходы противника, который приводит к гарантированной победе первого игрока за конечное время. Позиция называется проигрышной, если либо игрок уже проиграл, либо как бы не походил игрок, после этого у его соперника будет алгоритм победы. Другими словами, позиция является проигрышной, если либо игрок вообще не может выполнить ход, либо любой ход переводит игру в выигрышную позицию для соперника. Можно доказать, что позиция является выигрышной, тогда и только тогда, когда существует хотя бы один ход, переводящий позицию в проигрышную (для соперника).
Например, в шахматах проигрышной будет позиция мата — допустимых ходов вообще нет, выигрышной — позиция мата в один ход. Т.е. если есть хотя бы один ход, после которого сопернику будет поставлен мат, проигрышной будет ситуация, где как бы мы не ходили, у соперника будет возможность поставить мат в один ход. Соответственно выигрышной — мат в два хода и т.д. Правда в шахматах имеется ситуация пата и другие ничейные ситуации. В игре ним такое невозможно. Каждый ход игрока уменьшает количество зерен на игровом поле, и рано или поздно их не останется и один из игроков проиграет.

Итак, позиция [latex](0)[/latex], в которой нет камней вообще проигрышная, позиция [latex](n)[/latex], где [latex]n[/latex] — произвольное натуральное число — размер единственной кучки, выигрышная. Докажем, что ситуация [latex](a,b)[/latex], в которой есть две кучки по [latex]a[/latex] и [latex]b[/latex] зерен, проигрышная тогда и только тогда, когда [latex]a=b[/latex]. Воспользуемся индукцией по числу камней в минимальной из кучек. Ситуация [latex](1,1)[/latex] как мы уже видели проигрышная, соответственно из [latex](a,1)[/latex] и [latex](1,b)[/latex] в нее можно попасть и они выигрышные. Далее из [latex](a,a)[/latex] можно попасть только в позиции выигрышную позицию [latex](a)[/latex] или позиции [latex](a,b)[/latex] или [latex](b,a)[/latex], где [latex] b < a [/latex], выигрышные по индукционному предположению. Наконец ситуацию [latex](a,b)[/latex], где [latex]a\neq b[/latex], можно перевести или в [latex](a,a)[/latex] или в [latex](b,b)[/latex], проигрышные для соперника, поэтому исходная ситуация [latex](a,b)[/latex] — выигрышная.

А вот правильно поступила ли землеройка переведя ситуацию [latex]\left(3,2,1\right)[/latex] в выигрышную для крота [latex]\left(2,1\right)[/latex]? Был ли у землеройки выигрышный ход или позиция [latex]\left(3,2,1\right)[/latex] — изначально проигрышная? Это определить уже не так просто… Как Вы думаете?

Функция Шпрага-Гранди

Опять вернемся к совсем элементарной задаче — ниму с одной кучкой. Оказывается она исследована нами не до конца. Позиция с нулем зерен проигрышная — из нее нельзя перевести своим ходом соперника в проигрышную ситуацию. Поставим в соответствие такой позиции число 0. Будем называть это значение результатом применения функции Шпрага-Гранди к этой позиции или просто числом Шпрага-Гранди для позиции. Ситуация с одним зерном выигрышная — можно перевести соперника в проигрышную ситуацию (т.е. ситуацию с числом Шпрага-Гранди равным нулю). Тогда сопоставим этой ситуации число Шпрага-Гранди равное 1. Ситуация с двумя зернами тоже выигрышная — но она принципиально другая, так как кроме очевидного хода взять все зерна, есть еще ход взять одно зерно. Первый ход переводит игру в позицию с числом Шпрага-Гранди 0, а второй — в позицию с числом 1. Тогда сопоставим игровой ситуации с двумя зернами число 2.

Как Вы думаете, какое чему равна функция Шпрага-Гранди для позиции с тремя зернами.

В общем случае, определим функцию Шпрага-Гранди [latex] G : P \to \mathbb{N}_0 [/latex], где [latex]P[/latex] — множество игровых позиций, [latex]\mathbb{N}_0=\left\{0,1,2,3,4,\ldots\right\}[/latex] — множество целых неотрицательных чисел, по формуле

[latex]G(x)=\min\left\{n\in\mathbb{N}_0: n\neq G(y), y\in F(x)\right\}[/latex]

где [latex]x[/latex] — игровая позиция, для которой считается функция, [latex]F(x)[/latex] — множество позиций, в которые можно перейти непосредственно из позиции [latex]x[/latex] за один ход, [latex]n[/latex] — некоторое целое неотрицательное число, не равное значению ни одной из функций Шпрага-Гранди [latex] G [/latex] от позиций, в которые можно перейти за один ход из [latex]x[/latex]. Функция Шпрага-Гранди выбирает минимальное из таких чисел [latex]n[/latex]. Таким образом, функция Шпрага-Гранди равна нулю для позиций, для которых нет ни одного разрешенного хода и вычисляется рекурсивно для остальных позиций.

Свойства функции Шпрага-Гранди:

1. Позиция является проигрышной тогда и только тогда, когда ее число Шпрага-Гранди равно нулю.
2. Если функция Шпрага-Гранди не равна нулю, то обязательно существует ход, переводящий позицию в позицию с числом Шпрага-Гранди равным нулю (т.е. проигрышную для соперника). Выигрышной стратегией и будет делать каждый раз такие ходы.
3. Более того, если число Шпрага-Гранди равно [latex] n [/latex] и больше нуля, то для любого числа [latex] m [/latex] такого, что [latex] 0 \leq m < n [/latex], существуют ход переводящий позицию в новую позицию с числом Шпрага-Гранди равным [latex] m [/latex].

По индукции доказывается, что для игры «ним с одной кучкой», числа Шпрага-Гранди равны размеру кучки.

Давайте проанализируем еще одну игру, очень похожую на ним. Запретим землеройке и кроту cъедать более 3 зерен за раз. То есть, можно съесть одно, два или три зерна. По прежнему, кому нечего съесть — тот проиграл. Тогда проигрышной будет позиция с нулем зерен, а выигрышной — с одним, двумя, или тремя. Как Вы думаете если у Вас четыре зерна — проигрышная ли это позиция в данной модифицированной игре?

Как Вы думаете, какие позиции проигрышные и почему?

Давайте посчитаем числа Шпрага-Гранди для этой игры: для нуля зерен получаем ноль по определению фукции Шпрага-Гранди, для одного зерна можно перейти только в позицию с нулем, значит фукция Шпрага-Гранди от позиции с одним зерном равна 1, для двух зерен появляется выбор, перейти в позицию с числом Шпрага-Гранди равным нулю или единице, значит фукция Шпрага-Гранди от позиции с двумя зернами равна 2, и т.д. Неужели ничего не изменилось? Где эта закономерность, найденная для нима, нарушается?

Какими будут дальнейшие числа Шпрага-Гранди?

Дальше возникает следующий вопрос — а если кучек в игре ним несколько, можно ли быстро посчитать число Шпрага-Гранди для этой позиции? А также пока непонятно зачем вообще нужна функция Шпрага-Гранди, если для каждой позиции вроде как достаточно знать проигрышная она или выигрышная? Сейчас увидим…

Сумма игр

Представим теперь, что у нас есть несколько игр, и на выбор можно сделать ход в любой из них. Например, крот принес сразу три кучки зерен — с тремя, двумя и одним зерном. Землеройка должна вначале выбрать кучку, из которой она будет брать зерна, а потом взять любое количество зерен. Фактически землеройка из нескольких элементарных игр «ним» выбирает одну и делает ход только в ней. Даже если землеройка забирает все элементы кучки (т.е. одна из игр кончается), то это не конец всей игры. Вся игра кончается только тогда, когда закончена последняя из элементарных игр. Крот выбирает кучки по своему усмотрению, никак не зависимо от землеройки и тоже делает ход.

Итак назовем суммой нескольких игр такую игру, где игроки по очереди:

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

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

Итак ним, в который играют землеройка и крот, является суммой нескольких элементарных игр ним. Каждой кучке соответствует своя элементарная игра ним.

Как Вы думаете сложно ли найти число Шпрага-Гранди суммы игр? Оказывается очень просто. Для этого нам потребуется понятие xor-суммы, т.е. порязрядного суммирования чисел в двоичной системе без переноса в следующие разряды. Каждый разряд чисел обрабатывается независимо при помощи сложения по модулю 2. В языке C++ такая операция обозначается шляпкой (^), а в математике знаком [latex]\oplus[/latex].

Теорема. Число Шпрага-Гранди суммы игр равно xor-сумме чисел Шпрага-Гранди для каждой игры.

Значит ситуация в сумме игр проигрышная тогда и только тогда, когда xor-сумма равна нулю.

Наконец-то задача, которая предлагается Вам.

Задача Перед землеройкой лежит несколько кучек зерен и она может взять любое число зерен из любой кучки (вводится количество кучек и размер каждой). Из какой кучки и сколько зерен она должна взять? Если выигрышного хода нет, написать «Все равно я проиграю!».

Задача Перед землеройкой опять лежит несколько кучек зерен и но теперь она, как и крот, может съесть не более половины любой кучки зерен. Игра кончается, если игроку брать нечего. Из какой кучки и сколько зерен землеройка должна есть? Если выигрышного хода нет, написать «Все равно я проиграю!».

Что же можно еще почитать на эту тему?

Можно начать с интересной статьи про игру ним и теорию игр в научно-популярном журнале «Потенциал».

Если душа требует серьёзного продолжения, то можно посмотреть:

• Функция Шпрага-Гранди
• Nimber

А вот уже и совсем серьезные работы :

• А. Шень, Игры и стратегии с точки зрения математики — книга по данной тематике
• Андрей Станкевич, Игры на графах — очень крутая статья Станкевича с упором на четкие математические формулировки и доказательства, будет интересна для людей, которые серьезно хотят заниматься олимпиадным программированием или научными исследованиями на эту тематику!

Related Images: