Czym jest Nim Fibonacciego?
W Nim Fibonacciego gra się jednym stosem. Pierwszy gracz może zabrać dowolną liczbę żetonów oprócz całego stosu. Potem każdy ruch zabiera co najmniej jeden żeton i najwyżej dwa razy tyle, ile przeciwnik właśnie zabrał. Gracz, który zabierze ostatni żeton, wygrywa: w tę grę zawsze gra się normalnie, więc przełącznik misère i opcja stosów początkowych ze standardowej gry nie mają zastosowania.
Stos ma 10 (mały), 15 (średni, domyślny) lub 20 (duży) żetonów, co wybierasz jako rozmiar w ustawieniach stołu. Limit rośnie i maleje wraz z grą: duże zabranie pozwala przeciwnikowi zabrać jeszcze więcej, a małe trzyma go na krótkiej smyczy, więc gra toczy się o wielkość następnego limitu w tym samym stopniu co o stos.
Zmiany zasad
| Zasada | Nim (standard) | Nim Fibonacciego |
|---|---|---|
| Stosy | Nim (standard)Kilka stosów: domyślnie 1, 3, 5 i 7 żetonów albo inny zestaw wybrany w ustawieniach stołu. | Nim FibonacciegoJeden stos 10, 15 (domyślnie) lub 20 żetonów, wybierany jako rozmiar w ustawieniach stołu. |
| Pierwszy ruch | Nim (standard)Zabierz dowolną liczbę żetonów z jednego stosu, łącznie z całym stosem. | Nim FibonacciegoZabierz dowolną liczbę żetonów oprócz całego stosu. |
| Kolejne ruchy | Nim (standard)W każdym ruchu zabierz dowolną liczbę żetonów z jednego stosu. | Nim FibonacciegoZabierz co najmniej 1 i najwyżej dwa razy tyle, ile przeciwnik zabrał w poprzednim ruchu, i nie więcej, niż zostało. |
| Cel | Nim (standard)Domyślnie misère: kto zabierze ostatni żeton, przegrywa. W ustawieniach można przełączyć na grę normalną, w której zabranie ostatniego żetonu wygrywa. | Nim FibonacciegoZawsze gra normalna: kto zabierze ostatni żeton, wygrywa. |
| Wygrywająca gra | Nim (standard)Zostaw stosy z sumą nim (bitowym XOR ich wielkości) równą zero, z niuansem w końcówce misère. | Nim FibonacciegoZapisz stos jako sumę liczb Fibonacciego, z których żadne dwie nie sąsiadują w ciągu, i zabierz najmniejszą z nich, gdy limit na to pozwala. Pierwszy gracz przegrywa przy najlepszej grze dokładnie wtedy, gdy stos początkowy jest liczbą Fibonacciego; 10, 15 i 20 nimi nie są, więc pierwszy gracz może wygrać. |
Historia
Michael J. Whinihan opisał Nim Fibonacciego w 1963 roku w The Fibonacci Quarterly i przypisał grę Robertowi E. Gaskellowi, matematykowi z Oregon State University. Nazwa pochodzi od roli, jaką w rozwiązaniu odgrywają liczby Fibonacciego 1, 2, 3, 5, 8, 13, 21 i tak dalej.
Metoda wygranej opiera się na tym, co dziś nazywa się twierdzeniem Zeckendorfa: każda dodatnia liczba całkowita jest sumą liczb Fibonacciego, z których żadne dwie nie są kolejne, na dokładnie jeden sposób. Twierdzenie nosi imię Édouarda Zeckendorfa, choć Gerrit Lekkerkerker opublikował je już w 1952 roku.