April 16 2021 09:02:10
Навигация
Последние статьи
· Samsung ATADS30EBE о...
· 1942-1943 гг. Сталин...
· Гингивит - причины, ...
· S.T. SB35-62-1 обзор...
· Motorola PH252040I1 ...
· Panasonic VSK0593 - ...
· Jebao AP-333LV обзор...
· Многоцелевой Бе-200,...
· Центр Гидроавиации, ...
· Иглы для швейной маш...
· Хань Юй и Лю Цзун-юа...
· Шуберт Аве Мария - ноты
· Н.В. Гоголь Пьесы - ...
· 1943 - Новороссийска...
· 1877 - Самарское знамя
И все-таки, Гранди! - математическая смекалка

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

 

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

Последние комментарии
Новости
Где-то читал, что Соко...
[b]Морковкин:[/b] В...
[b]Vip-Tip:[/b] Доц...
[b][big]Кстати, насчет...
Там тоже все разные. М...
Статьи
Честно говоря - ничего...
проблема замок приваре...
Спасибо за ответ! Я к...
Вот именно - можно поп...
Konstantin73 - непрофе...
Фотогалерея
Вот здесь я начал выкл...
Я думаю это не украинц...
Печальное зрелище... д...
Lexa-SU не уподобляйте...
А еще были ништяк - бл...
Отдельные страницы
В 7 дейс есть интересн...
Все профукали - русски...
Толян: — В результа...
Oskar: Вроде бы все ус...
У них другой менталите...
Счетчики


Яндекс.Метрика
8,245,997 уникальных посетителей