= Fibonacci Nim
{c}
{title2=$r<z(n)\ \Longleftrightarrow\ \text{losing}$}
<Fibonacci Nim> is a <normal play> <impartial game> on one heap. Start with $N\ge2$ counters. The first move removes between $1$ and $N-1$ counters; thereafter a move removes at least one and at most twice the number just removed by the opponent, without exceeding the remaining heap. Taking the last counter wins.
For a position with $n>0$ counters and permitted maximum $r$, let $z(n)$ be the smallest <Fibonacci number> appearing in the <Zeckendorf representation> of $n$, using the sequence $1,2,3,5,8,\ldots$. The position is losing exactly when $r<z(n)$. If $r\ge z(n)$, removing $z(n)$ is a winning move. When this does not empty the heap, the next smallest summand exceeds $2z(n)$, so the opponent's new limit is too small. Conversely, the Zeckendorf subtraction lemma gives $z(n-t)\le2t$ whenever $0<t<z(n)$, so every legal move from a losing position leaves a winning one.<Fibonacci Nim by Michael J. Whinihan>[Pages 9–12: rules, least-summand criterion and proof]{ref}
Initially $r=N-1$, so the losing initial heap sizes are precisely the <Fibonacci numbers>. For example, $10=8+2$: take $2$, leaving the opponent $8$ counters and a limit of $4$, a losing position. The move limit is part of the state; heap size alone does not determine later positions.
Back to article page
