June 29 2022 17:15:18
Навигация
Последние статьи
· JAL - Japan Airlines...
· Япония XVI века глаз...
· Ajax DoorProtect дат...
· Амперметры и вольтме...
· Компьютерный блоки п...
· SD-9411CPDDBGD плата...
· Основа экономической...
· Рыбный жир - БАД от ...
· Покупай выгодно!
· Надежный партнер - г...
· Деловая репутация - ...
· Эрозивно-язвенный га...
· Сладкие подарки на Н...
· Где найти контрактны...
· Россия 2022 - оборуд...
И все-таки, Гранди! - математическая смекалка

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

 

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

Последние комментарии
Новости
Еще вчера глупенькие у...
Сейчас Мотор сич не бо...
Америка страна мошенни...
Сперва уничтожают пром...
:o Турция сама себя на...
Статьи
Заказчик не оплатил - ...
Статья рекламная... но...
Очень опасаюсь такое б...
Как же сильно они выли...
Я такие лампочки по ве...
Фотогалерея
Раньше и Казахстан и г...
Не могу понять - почем...
Во времена СССР натура...
А - такой маленький пр...
Скоро мы все это снова...
Отдельные страницы
Днем 24 мая 2022 года ...
Сейчас снова начали ст...
Это кошмар... Казахста...
А вывод очень скупой -...
Этих Гизов разрекламир...
Счетчики


Яндекс.Метрика
10,174,669 уникальных посетителей