Proof of winning strategy in Fibonacci Nim

Question

I have spent some time messing around with various factors, but have got effectively nowhere, due to how relatively new I am to this form.

Brief explanation of Fibonacci Nim: The game involves a pile on coins where upon players alternate taking a number of coins off the pile, each player may take no more than double what the previous player took. The first player may not take the whole pile. The player to take the last coin wins.

I would greatly appreciate if anyone could give an explanation of the proof or provide a link to an explanation of the proof (found a couple papers talking about the problem, but as with such things the explanations are not really accessible, and often vary).

Answer 1

To find a winning strategy for this problem, we need to make use of Zeckendorf's theorem: any number can be written uniquely as a descending sum of non-adjacent Fibonacci numbers, in which the last is at least $F_2$.

For example, $32$ can be written as $21 + 8 + 3 = F_8 + F_6 + F_4$, which is its Zeckendorf representation. It can also be written as $21 + 5 + 3 + 2 + 1 = F_8 + F_5 + F_4 + F_3 + F_2$, but this is not valid because $F_5$ and $F_4$ (as well as $F_4$ and $F_3$, or $F_3$ and $F_2$) are adjacent Fibonacci numbers.

The reason this is relevant at all is that Fibonacci numbers have the following property: for any $n \ge 2$, $F_{n+2} > 2F_n$. (Prove this by induction.) So in the Zeckendorf representation, each Fibonacci number used is more than twice the next.

On to the actual game. We can represent a position in Fibonacci Nim by a pair $(\ell, r)$ where:

• $\ell$ is the limit: the largest number of coins that can be taken, and
• $r$ is the remainder: the number of coins left.

If we start with $n$ coins, that position can be represented as $(n-1,n)$.

Claim. A position $(\ell,r)$ is a win for the first player if, in the Zeckendorf representation of $r$, the smallest Fibonacci number is at most $\ell$. (Call such positions comfortable to make them easier to refer to.)

Proof. All positions with $\ell \ge r$, in which the first player can take all the remaining coins, are obviously comfortable, so the claim is true in that case. It's enough to prove that:

1. From every comfortable position, some move can produce an uncomfortable position.
2. From every uncomfortable position, all moves lead to comfortable positions. (In other words, to produce an uncomfortable position, we must be in a comfortable position.)

Statement 1 holds because if $r$ has Zeckendorf representation $F_{a_k} + \dots + F_{a_1}$, with $a_{i+1} \ge a_i + 2$ and $F_{a_1} \le \ell$, we can take away $F_{a_1}$ coins. Then the smallest Fibonacci number in what's left is $F_{a_2}$, the limit is $2F_{a_1}$, and $F_{a_2} > 2F_{a_1}$.

Statement 2 holds because, if we move from $(\ell, r)$ to $(2x, r-x)$ where the smallest Fibonacci number in the Zeckendorf reprentation of $r-x$ is bigger than $2x$, then we can concatenate the Zeckendorf representations of $r-x$ and $x$ to get a Zeckendorf representation of $r$. So if we move to an uncomfortable position, we must have done so by taking away the sum of the last few Fibonacci numbers in the Zeckendorf representation of $r$. In particular, we took away a number at least as large as the smallest Fibonacci number in the Zeckendorf representation of $r$, so we must have been in a comfortable position.

So the optimal strategy, starting from a comfortable position, is to always put your opponent into an uncomfortable one. Whatever move you make, they will be forced to give you an uncomfortable position back, and this repeats until you're in a position where you can take all the coins.

In particular, the position $(n-1,n)$ - a starting position where your only constraint is that you can't take all the coins - is comfortable unless $n$ is a Fibonacci number. So all Fibonacci number positions are second player wins, and all other positions are first player wins.