What is Fibonacci Nim?
Fibonacci Nim is played with a single heap. The first player may take any number of objects except the whole heap. After that, each move takes at least one object and at most twice as many as the opponent just took. The player who takes the last object wins: the game is always played the normal way round, so the misère switch and the starting piles option of the standard game do not apply.
The heap holds 10 (small), 15 (medium, the default) or 20 (large) objects, chosen as the size in the table setup. The limit grows and shrinks with the play: a big take lets the opponent take even more, while a small one keeps them on a short leash, so the game is a fight over the size of the next limit as much as over the heap.
Rule changes
| Rule | Standard Nim | Fibonacci Nim |
|---|---|---|
| Heaps | Standard NimSeveral heaps: 1, 3, 5 and 7 objects by default, or another set chosen in the table setup. | Fibonacci NimOne heap of 10, 15 (default) or 20 objects, chosen as the size in the table setup. |
| First move | Standard NimTake any number of objects from one heap, the whole heap included. | Fibonacci NimTake any number of objects except the whole heap. |
| Later moves | Standard NimTake any number of objects from one heap, every turn. | Fibonacci NimTake at least 1 and at most twice as many as the opponent took on the move before, and no more than is left. |
| Goal | Standard NimMisère play by default: whoever takes the last object loses. The setup can switch to normal play, where taking the last object wins. | Fibonacci NimAlways normal play: whoever takes the last object wins. |
| Winning play | Standard NimLeave the heaps with a nim-sum (the bitwise XOR of their sizes) of zero, with a twist in the misère endgame. | Fibonacci NimWrite the heap as a sum of Fibonacci numbers, no two of them next to each other in the sequence, and take the smallest of them when the limit allows. The first player loses with best play exactly when the starting heap is a Fibonacci number; 10, 15 and 20 are not, so the first player can win. |
History
Michael J. Whinihan described Fibonacci Nim in 1963 in The Fibonacci Quarterly and credited the game to Robert E. Gaskell, a mathematician at Oregon State University. Its name comes from the part the Fibonacci numbers 1, 2, 3, 5, 8, 13, 21 and so on play in the solution.
The winning method rests on what is now called Zeckendorf's theorem: every positive whole number is a sum of Fibonacci numbers, no two of them consecutive, in exactly one way. The theorem is named after Édouard Zeckendorf, although Gerrit Lekkerkerker had already published it in 1952.