# Definition:Fibonacci Nim

Jump to navigation Jump to search

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