Фибоначчи это

Фибоначчи ним — математическая игра на вычитание , вариант игры ним . Игроки поочередно вынимают монеты из стопки, на каждом ходу беря не более двух монет больше, чем на предыдущем ходу, и выигрывают, забирая последнюю монету. Числа Фибоначчи играют важную роль в его анализе; в частности, первый игрок может выиграть тогда и только тогда, когда начальное количество монет не является числом Фибоначчи. Полная стратегия лучше всего подходит для игр с одной стопкой фишек, но не для вариантов игры с несколькими стопками.

Правила и история

В игру Фибоначчи ним играют два игрока, которые поочередно вынимают из стопки монеты или другие жетоны. На первом ходу игроку не разрешается взять все монеты, а на каждом последующем ходу количество убираемых монет может быть любым числом, не более чем в два раза превышающим количество предыдущих ходов. Согласно правилам обычной игры , побеждает игрок, забравший последнюю монету. ^[1]

Впервые игра была описана Майклом Дж. Уиниханом в 1963 году, приписав ее изобретение математику из Университета штата Орегон Роберту Э. Гаскеллу. Он называется «ним Фибоначчи», потому что числа Фибоначчи играют важную роль в его анализе. ^[2]

Эту игру следует отличать от другой игры, также называемой «Фибоначчи ним», в которой игроки могут удалять любое количество монет Фибоначчи за каждый ход. ^[3]

Стратегия

Стратегия лучшей игры в Фибоначчи-ним предполагает представление текущего количества монет как суммы чисел Фибоначчи . ^[2] Существует много способов представления чисел в виде сумм чисел Фибоначчи, но только одно представление, в котором каждое число Фибоначчи используется не более одного раза и избегается последовательных пар чисел Фибоначчи; это уникальное представление известно как представление Цекендорфа . Например, представление Зекендорфа числа 10 равно 8 + 2; хотя 10 также можно представить в виде суммы чисел Фибоначчи другими способами, например 5 + 5 или 5 + 3 + 2, эти другие способы не соответствуют условию использования каждого числа Фибоначчи только один раз и избегания последовательных пар чисел Фибоначчи, таких как как пары 2, 3 и 3, 5. Представление Цекендорфа любого числа можно найти с помощью жадного алгоритма , который многократно вычитает максимально возможное число Фибоначчи, пока не достигнет нуля. ^[4]

Стратегия игры также включает в себя число, называемое «квота», которое можно обозначить как $q$ . Это максимальное количество монет, которое на данный момент можно удалить. При первом ходе можно убрать все монеты, кроме одной, поэтому, если количество монет равно $n$ , квота равна $q = n - 1$ . При последующих ходах квота в два раза превышает предыдущий ход. ^[2]

Основываясь на этих определениях, игрок, который собирается сделать ход, может выиграть, когда $q$ больше или равно наименьшему числу Фибоначчи в представлении Цекендорфа, и проиграет (при лучшей игре противника) в противном случае. В выигрышной позиции всегда выигрышным ходом является удаление всех монет (если это разрешено) или иным образом удаление количества монет, равного наименьшему числу Фибоначчи в представлении Цекендорфа. Когда это возможно, противостоящий игрок обязательно столкнется с проигрышной позицией, поскольку новая квота будет меньше наименьшего числа Фибоначчи в представлении Зекендорфа оставшегося количества монет. ^[2] Возможны и другие выигрышные ходы. ^[5] Однако из проигрышной позиции все ходы приведут к выигрышным позициям. ^[2]

Зекендорфское представление числа Фибоначчи состоит из этого одного числа. Таким образом, когда стартовая стопка монет имеет число Фибоначчи $n$ , наименьшее число Фибоначчи в представлении Цекендорфа составляет всего лишь $n$ , что больше, чем стартовая квота $n - 1$ . Следовательно, число Фибоначчи в качестве стартовой стопки является проигрышным для первого игрока и выигрышным для второго игрока. Однако любое начальное количество монет, не являющееся Фибоначчи, имеет меньшие числа Фибоначчи в своем представлении Цекендорфа. Эти числа не превышают стартовую квоту, поэтому, если начальное количество монет не является числом Фибоначчи, первый игрок всегда может выиграть. ^[1]

Пример

Например, предположим, что изначально имеется 10 монет. ^[6]

Представление Цекендорфа 10 равно 10 = 8 + 2, а начальная квота равна 9, что больше, чем наименьшее число Фибоначчи 2 в представлении Цекендорфа, поэтому первый игрок может выиграть. Одним из выигрышных ходов первого игрока будет удаление наименьшего числа Фибоначчи в этом представлении, 2, оставив 8 монет.
После этого хода остается 8 монет, при этом представление Цекендорфа равно 8, а новая квота равна 4, что означает, что второй игрок может удалить не более 4 монет, чего недостаточно для достижения наименьшего числа в представлении Цекендорфа. Удаление 3 или 4 монет позволит первому игроку немедленно выиграть; предположим, что вместо этого второй игрок берет 2 монеты.
В результате остается 6 = 5 + 1 монет с квотой 4, что больше, чем 1 в представлении Цекендорфа. Первый игрок снова может взять наименьшее число Фибоначчи в этом представлении, 1, оставив 5 монет.
При стопке из 5 монет представительство Зекендорфа равно 5, но квота равна 2, меньшему числу. Второй игрок мог бы взять две монеты, но это снова немедленно проиграет, поэтому предположим, что второй игрок берет только одну монету.
После этого хода количество монет равно 4 = 3 + 1, а квота равна 2. Первый игрок снова берет наименьшее число Фибоначчи в представлении Цекендорфа, 1, оставляя 3 монеты.
Теперь независимо от того, возьмет ли второй игрок одну или две монеты, следующим ходом игру выиграет первый игрок.

Несколько свай

Фибоначчи ним — это беспристрастная игра , в которой ходы, доступные из любой позиции, не зависят от личности игрока, который собирается сделать ход. Следовательно, теорему Спрага-Грунди можно использовать для анализа расширения игры, в которой имеется несколько стопок монет, и каждый ход удаляет монеты только из одной стопки (максимум в два раза больше, чем предыдущий ход из той же стопки). . Для этого расширения необходимо вычислить ним-ценность каждой стопки; Ценность игры с несколькими стопками равна ним-сумме этих ним-стоимостей. Однако полное описание этих значений неизвестно. ^[7]

Другой вариант игры с несколькими стопками, который также был изучен, ограничивает количество камней в каждом ходе вдвое больше, чем в предыдущем ходе, независимо от того, был ли этот предыдущий ход в ту же стопку. ^[8]

Ссылки

^ Jump up to: ^а ^б Вайда, Стивен (2007), «Фибоначчи ним» , «Математические игры и как в них играть » , Dover Books on Mathematics, Courier Corporation, стр. 28–29, ISBN 9780486462776
^ Jump up to: ^а ^б ^с ^д ^и Уинихан, Майкл Дж. (1963), «Фибоначчи Ним» (PDF) , Fibonacci Quarterly , 1 (4): 9–13
^ Об игре на вычитание чисел Фибоначчи из монет см. Альфред, Брат У. (1963), «Изучение чисел Фибоначчи» (PDF) , Fibonacci Quarterly , 1 (1): 57–63 , «Исследовательский проект: Фибоначчи ним», стр. 63; Понд, Джереми К.; Хауэллс, Дональд Ф. (1963), «Больше о Фибоначчи ним» (PDF) , Fibonacci Quarterly , 1 (3): 61–62
^ Грэм, Рональд Л .; Кнут, Дональд Э .; Паташник, Орен (1994), Конкретная математика (2-е изд.), Аддисон-Уэсли, стр. 295–296, ISBN 0-201-55802-5
^ Аллен, Коди; Пономаренко, Вадим (2014), «Ним Фибоначчи и полная характеристика выигрышных ходов», Involve , 7 (6): 807–822, doi : 10.2140/involve.2014.7.807
^ Тот факт, что 2 является уникальным выигрышным ходом из этой стартовой позиции, а также представления Зекендорфа всех размеров стопки, возникающие в этом примере, можно увидеть в Allen & Ponomarенко (2014) , Таблица 1, стр. 818.
^ Ларссон, Урбан; Рубинштейн-Сальзедо, Саймон (2016), «Значения Гранди Фибоначчи ним», Международный журнал теории игр , 45 (3): 617–625, arXiv : 1410.0332 , doi : 10.1007/s00182-015-0473-y , MR 3538534 , S2CID 206890376
^ Ларссон, Урбан; Рубинштейн-Сальзедо, Саймон (2018), «Глобальный Фибоначчи ним», Международный журнал теории игр , 47 (2): 595–611, doi : 10.1007/s00182-017-0574-x , MR 3842045 , S2CID 52073784

[v07-1] Jump up to: ^а ^б Вайда, Стивен (2007), «Фибоначчи ним» , «Математические игры и как в них играть » , Dover Books on Mathematics, Courier Corporation, стр. 28–29, ISBN 9780486462776

[w63-2] Jump up to: ^а ^б ^с ^д ^и Уинихан, Майкл Дж. (1963), «Фибоначчи Ним» (PDF) , Fibonacci Quarterly , 1 (4): 9–13

[subfib-3] Об игре на вычитание чисел Фибоначчи из монет см. Альфред, Брат У. (1963), «Изучение чисел Фибоначчи» (PDF) , Fibonacci Quarterly , 1 (1): 57–63 , «Исследовательский проект: Фибоначчи ним», стр. 63; Понд, Джереми К.; Хауэллс, Дональд Ф. (1963), «Больше о Фибоначчи ним» (PDF) , Fibonacci Quarterly , 1 (3): 61–62

[gkp94-4] Грэм, Рональд Л .; Кнут, Дональд Э .; Паташник, Орен (1994), Конкретная математика (2-е изд.), Аддисон-Уэсли, стр. 295–296, ISBN 0-201-55802-5

[ap14-5] Аллен, Коди; Пономаренко, Вадим (2014), «Ним Фибоначчи и полная характеристика выигрышных ходов», Involve , 7 (6): 807–822, doi : 10.2140/involve.2014.7.807

[6] Тот факт, что 2 является уникальным выигрышным ходом из этой стартовой позиции, а также представления Зекендорфа всех размеров стопки, возникающие в этом примере, можно увидеть в Allen & Ponomarенко (2014) , Таблица 1, стр. 818.

[lr16-7] Ларссон, Урбан; Рубинштейн-Сальзедо, Саймон (2016), «Значения Гранди Фибоначчи ним», Международный журнал теории игр , 45 (3): 617–625, arXiv : 1410.0332 , doi : 10.1007/s00182-015-0473-y , MR 3538534 , S2CID 206890376

[lr18-8] Ларссон, Урбан; Рубинштейн-Сальзедо, Саймон (2018), «Глобальный Фибоначчи ним», Международный журнал теории игр , 47 (2): 595–611, doi : 10.1007/s00182-017-0574-x , MR 3842045 , S2CID 52073784

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]