November 27 2021 02:48:31
Навигация
Последние статьи
· Маркирование продукц...
· Разборка Nokia C5-00
· Особые свойства чая ...
· Инструкция по разбор...
· Новая космическая пр...
· SH2003B весы электро...
· КГМ 12-40 галогенная...
· Банда Пожарники, Анг...
· Проблемы революционн...
· Бой под Улус-Кертом ...
· Правила выбора армат...
· Зима. Жара FM. Музыка
· Виртуальный телефонн...
· Бариста: все про про...
· Выключатель проходно...
И все-таки, Гранди! - математическая смекалка

И все-таки, Гранди! - математическая смекалка

 

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

Автор Алексей ТЕТЕРКО (Черкассы)

Комментарии
Нет комментариев.
Добавить комментарий
Пожалуйста, авторизуйтесь для добавления комментария.
Реклама
Авторизация
Логин

Пароль



Вы не зарегистрированы?
Нажмите здесь для регистрации.

Забыли пароль?
Запросите новый здесь.
Google

Последние комментарии
Новости
От этих жуликов - иног...
Давно американцы таког...
Дешевый старикашка, ко...
И те и другие хороши! ...
Это американские бабск...
Статьи
Ну вот эти - это хорош...
Эх - бывали дни веселые!
А что - это еще очень ...
Как же - был и у меня ...
Чем-то Автора статьи с...
Фотогалерея
Конечно, во время Втор...
Ну - такой орден ценно...
Вот здесь я начал выкл...
Я думаю это не украинц...
Печальное зрелище... д...
Отдельные страницы
Немного поправлю: [...
В 80-е годы мой дядя в...
Прямо дохнуло стариной...
Идеализация фашистов и...
В 7 дейс есть интересн...
Счетчики


Яндекс.Метрика
9,254,913 уникальных посетителей