Ним Фибоначчи - это математическая игра на вычитание , вариант игры ним . Впервые игра была описана Майклом Дж. Уиниханом в 1963 году, который приписывает свое изобретение Роберту Э. Гаскеллу. Он называется нимом Фибоначчи, потому что числа Фибоначчи широко используются в его анализе. [1]
Правила [ править ]
В ним Фибоначчи играют два игрока, которые по очереди удаляют монеты или другие фишки из стопки. На первом ходу игроку не разрешается брать все монеты, а на каждом последующем ходу количество удаленных монет может быть любым числом, которое не более чем в два раза превышает предыдущий ход. Согласно обычному игровому соглашению , побеждает игрок, который берет последнюю монету. [2]
Эту игру следует отличать от другой игры, также называемой нимом Фибоначчи, в которой игроки могут убирать любое количество монет Фибоначчи на каждом ходу. [3]
Стратегия [ править ]
Оптимальная стратегия в ниме Фибоначчи (в соответствии с соглашением о нормальной игре) может быть описана с использованием представления Цекендорфа текущего количества монет как суммы непоследовательных чисел Фибоначчи и с использованием числа, называемого «квотой». Квота может быть обозначена q и определяется как максимальное количество монет, которое в настоящее время может быть удалено. На первом ходу все монеты, кроме одной, могут быть удалены, поэтому, если количество монет равно n, то квота равна q = n - 1 . При последующих ходах квота в два раза превышает предыдущий ход. Исходя из этих определений, данная позиция является проигрышной для игрока, который собирается двигаться, когда qменьше наименьшего числа Фибоначчи в представлении Цекендорфа, а в противном случае - выигрышная позиция. В выигрышной позиции всегда выигрышным ходом является удаление всех монет (если это разрешено) или удаление количества монет, равного наименьшему числу Фибоначчи в представлении Цекендорфа. Когда это возможно, противник обязательно столкнется с проигрышной позицией, потому что новая квота будет меньше наименьшего числа Фибоначчи в представлении Цекендорфа оставшегося количества монет. Из проигрышной позиции любое движение приведет к выигрышной позиции. [1]
В частности, когда начальная стопка содержит число монет Фибоначчи, представление Цекендорфа состоит из этого числа, а квота n - 1 меньше этого числа. Следовательно, начальная стопка такой формы проигрывает для первого игрока и выигрывает для второго игрока. Однако, если начальное количество монет не является числом Фибоначчи, первый игрок всегда может выиграть. [2] В этом случае стратегия на основе квот удалит наименьшее число в представлении Цекендорфа стартовой стопки, но в целом может быть несколько возможных выигрышных ходов. [4]
Пример [ править ]
Например, предположим, что изначально есть 10 монет. В представлении Цекондорфа 10 = 8 + 2, поэтому выигрышным ходом первого игрока будет удаление наименьшего числа Фибоначчи в этом представлении, 2, в результате чего останется 8 монет. Второй игрок может удалить не более 4 монет, но удаление 3 или более позволит первому игроку немедленно выиграть, поэтому предположим, что второй игрок берет 2 монеты. Это оставляет 6 = 5 + 1 монет, и первый игрок снова берет наименьшее число Фибоначчи в этом представлении, 1, оставляя 5 монет. Второй игрок может взять две монеты, но он снова немедленно проиграет, поэтому второй игрок берет только одну монету, оставляя 4 = 3 + 1. Первый игрок снова берет наименьшее число Фибоначчи в этом представлении, 1, оставляя 3 монеты. Теперь, независимо от того, берет ли второй игрок одну или две монеты,первый игрок выиграет игру следующим ходом.[5]
Множественные сваи [ править ]
Ним Фибоначчи - это беспристрастная игра, поскольку ходы, доступные из любой позиции, не зависят от личности игрока, который собирается двигаться. Таким образом, теорема Спрага-Гранди может использоваться для анализа расширения игры, в которой есть несколько стопок монет, и каждый ход удаляет монеты только из одной стопки (не более чем в два раза больше, чем предыдущий ход из той же стопки). . Для этого расширения необходимо вычислить минимальную стоимость каждой стопки; Ценность игры с множеством стопок - это ним-сумма этих ним-ценностей. Однако полное описание этих значений неизвестно. [6]
Другой вариант игры с несколькими стопками, который также был изучен, ограничивает количество камней в каждом ходу вдвое больше, чем в предыдущем, независимо от того, относился ли этот предыдущий ход к той же стопке. [7]
Ссылки [ править ]
- ^ a b Whinihan, Майкл Дж. (1963), "Fibonacci Nim" (PDF) , Fibonacci Quarterly , 1 (4): 9–13.
- ^ a b Вайда, Стивен (2007), «Fibonacci nim» , « Математические игры и как в них играть» , Dover Books on Mathematics, Courier Corporation, стр. 28–29, ISBN 9780486462776.
- ^ Об игре вычитания чисел Фибоначчи монет см. Альфред, Брат У. (1963), «Изучение чисел Фибоначчи» (PDF) , Fibonacci Quarterly , 1 (1): 57–63 , "Исследовательский проект: Фибоначчи ним", стр. 63; Пруд, Джереми С.; Хауэллс, Дональд Ф. (1963), «Подробнее о ниме Фибоначчи» (PDF) , Fibonacci Quarterly , 1 (3): 61–62 .
- ^ Аллен, Коди; Пономаренко, Вадим (2014), «Ним Фибоначчи и полная характеристика выигрышных ходов», Involve , 7 (6), doi : 10.2140 / include.2014.7.807
- ^ Тот факт, что 2 является уникальным выигрышным ходом из этой стартовой позиции, и представления Цекондорфа всех размеров стопки, возникающие в этом примере, можно увидеть в Allen & Ponomarenko (2014) , Таблица 1, стр. 818.
- ^ Ларссон, Урбан; Рубинштейна-Salzedo, Саймон (2016), "Гранди значения NIM Фибоначчи", Международный журнал теории игр , 45 (3): 617-625, Arxiv : 1410,0332 , DOI : 10.1007 / s00182-015-0473-у , MR 3538534 .
- ^ Ларссон, Урбан; Рубинштейна-Salzedo, Саймон (2018), "Global Фибоначчи NIM", Международный журнал теории игр , 47 (2): 595-611, DOI : 10.1007 / s00182-017-0574-х , MR 3842045
