И все-таки, Гранди! - математическая смекалка
1. Двое играют в следующую странную, о чем позднее, игру:
- у них есть кучка камней, причем камней нечетное число;
- они берут по-очереди камни из кучки, причем не более четырех за раз;
- так продолжается, пока всю кучку не разберут, и тогда победил тот, кто взял четное число камней.
На первый взгляд, игра не поддается анализу с помощью функции Гранди:
1. Состояние кучки не определяет положение в игре, т.к. важны еще камни игроков.
Но это легко устраняется, берем в качестве состояния игры тройку:
(n, m, p),
где n - число камней в кучке,
m - четность числа камней у игрока, чей ход,
p - четность числа камней у другого игрока.
В дальнейшем 0 - означает четное, а 1 - нечетное число камней.
Такое определение состояния игры восстанавливает симметрию между игроками, но возникает следующее затруднение:
2. Игра заканчивается, когда камней в куче нет, т.е. n=0. Но таких позиций у нас две (вспоминаем, что общее число камней нечетно):
(0,1,0) [1]
(0,0,1) [2]
Если позиция [1] удовлетворяет нашим понятиям о конце игры: хода нет, у игрока, который должен ходить, нечетное число камней, и он, следовательно, проиграл, то позиция [2] несколько странна: хода нет, но ходящий из нее не проиграл (!), ведь у него четное число камней...
Устраняем эту странность формально - считаем, что в позиции [2] начинающий может сделать пустой ход, переводя ее в позицию [1]. Т.е. на графе игры добавляем дугу:
(0,0,1) --> (0,1,0)
Теперь строим функцию Гранди, для чего рисуем кусок графа игры. Из каждой вершины выходят не более четырех дуг.
Рис. 1
Можно заметить разного рода симметрию этого графа, но это лирика... Определяем функцию Гранди на вершинах стандартным образом:
Gr((0,1,0))=0
Gr(x)=min(N0 \ {Gr(t) | t in Gx}),
где Gr(x) - значение функции Гранди в вершине x,
N0 - множество неотрицательных целых чисел,
Gx - множество концов дуг с началом в вершине x, или, это множество позиций, в которые можно перейти, сделав ход в позиции x.
Результат вычислений показан на том же рис. 1. - значения функции Гранди даны в кружках. Функция оказывается периодической с периодом длины 6, который обведен на рис. 1. тонким прямоугольником. Желающие могут сами доказать периодичность, а мы перейдем к формулам.
Периодичность означает следующее:
Gr((n,m,p))=Gr((a,m,p)),
где n=a (mod 6).
Так как в начале игры камней на руках нет, а в кучке нечетное число, то позиция имеет вид:
(n,0,0),
где n - нечетное.
Получаем соотношения:
Gr((n,0,0))=1, при n=5 (mod 6)
Gr((n,0,0))=3, при n=3 (mod 6)
Gr((n,0,0))=0, при n=1 (mod 6)
Кстати, в задаче 286 Кордемского n=27, т.е.
Gr((27,0,0))=Gr((3,0,0))=3,
начинающий выигрывает, и ход, переводящий игру в нулевую позицию, можно увидеть из графа - он эквивалентен ходу
(3,0,0) --> (1,0,0),
т.е. начинающий берет два камня.
Я в начале обмолвился о странности этой игры, но представим себе такой вариант: в куче есть протоны и электроны, выигрывает тот, у кого заряд меньше по модулю, т.е. ближе к нулю. А если еще добавить нейтроны,.. то можно вообразить себя богом-творцом.
По материалам задачи 286 из книги Кордемского "Математическая смекалка", издание 10-е, МДС, 1994
Автор Алексей ТЕТЕРКО (Черкассы) |
