Definition:Fibonacci Nim
Definition
Fibonacci nim is a two-person game whose rules are as follows:
- $(1): \quad$ The game starts with one pile of $n$ counters.
- $(2): \quad$ The first player removes a number of counters $c_1$ such that $1 \le c_1 < n$.
- $(3): \quad$ Each player takes it in turns to remove $c_n$ counters such that $1 \le c_n \le 2 c_{n - 1}$ where $c_{n - 1}$ is the number of counters taken in the other player's prevous move.
- $(3): \quad$ The person who removes the last counter (or counters) is the winner.
Examples
$11$ starting counters
Let a game of Fibonacci nim between player $\text A$ and player $\text B$ have a starting pile of $11$ counters.
$\text A$ removes $3$ counters, leaving $8$.
$\text B$ may remove up to $6$ counters, and takes $1$, leaving $7$.
$\text A$ may remove $1$ or $2$ counters, and takes $2$, leaving $5$.
$\text B$ may remove up to $4$ counters, and takes $1$, leaving $4$.
$\text A$ may remove $1$ or $2$ counters, and takes $1$, leaving $3$.
$\text B$ must remove either $1$ or $2$ counters, leaving $\text A$ in a position to take all the counters next turn.
$\text A$ wins.
$1000$ starting counters
Let a game of Fibonacci nim between player $\text A$ and player $\text B$ have a starting pile of $1000$ counters.
The optimal strategy for player $\text A$ is to take $13$ counters.
Also see
- Results about Fibonacci nim can be found here.
Source of Name
This entry was named for Leonardo Fibonacci.
Historical Note
The game of Fibonacci nim was reported by Michael J. Whinihan in $1963$ as being the invention of Robert E. Gaskell.
Sources
- 1963: Michael J. Whinihan: Fibonacci Nim (The Fibonacci Quarterly Vol. 1, no. 4: pp. 9 – 13)
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.8$: Fibonacci Numbers: Exercise $37$