# 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$