Fibonacci Nim/Examples/1000

From ProofWiki
Jump to navigation Jump to search

Example of Game of Fibonacci Nim

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.


Proof

Expressed in Zeckendorf representation:

$1000 = 987 + 13 = F_{16} + F_7$

That is:

$1000 = F_{k_1} + F_{k_2} + \cdots + F_{k_r}$

where $k_1 = 16$ and $k_2 = k_r = 7$.

The maximum number of counters that can be taken here is $1000 - 1 = 999$.

By Optimal Strategy for Fibonacci Nim, player $\text A$ can force a win if and only if it is possible to take $F_{k_r}$ counters.

In this case, $F_{k_r} = 13$.

$\blacksquare$


Sources