TAOCP 1.2.8 Exercise 37
Let a position be denoted by $(N,p)$, where $N$ is the number of chips remaining and $p$ is the number of chips removed on the preceding move.
Section 1.2.8: Fibonacci Numbers
Exercise 37. [M35] (R. E. Gaskell, M. J. Whinihan.) Two players compete in the following game: There is a pile containing $n$ chips; the first player removes any number of chips except that he cannot take the whole pile. From then on, the players alternate moves, each person removing one or more chips but not more than twice as many chips as the preceding player has taken. The player who removes the last chip wins. What is the best move for the first player to make if there are initially 1000 chips?
Verified: no
Solve time: -
Setup
Let a position be denoted by $(N,p)$, where $N$ is the number of chips remaining and $p$ is the number of chips removed on the preceding move. A legal move from $(N,p)$ consists of removing some number $q$ such that
$$ 1\le q\le \min(2p,N), $$
except that on the first move the player may remove any positive number less than $N$.
A position is called winning if the player to move can force a win; otherwise it is called losing.
The problem asks for the optimal first move when the initial pile contains $1000$ chips.
Solution
The key fact is that the losing positions are precisely those for which
$$ N\equiv 0 \pmod{\phi}, $$
in the sense made precise below by the Fibonacci representation of Exercise 34.
Define numbers
$$ H_k=F_{k+2}-1. $$
The first values are
$$ H_1=1,\qquad H_2=2,\qquad H_3=4,\qquad H_4=7,\qquad H_5=12,\ldots $$
We shall prove that the losing positions are exactly
$$ (H_k,F_k),\qquad k\ge1. $$
First consider $(H_k,F_k)$. Since
$$ H_k=F_{k+2}-1=F_{k+1}+F_k-1, $$
a legal move removes some number $q$ with
$$ 1\le q\le 2F_k. $$
The new position is
$$ (H_k-q,q). $$
Suppose this new position were also losing, say
$$ (H_k-q,q)=(H_j,F_j). $$
Then
$$ q=F_j $$
and
$$ H_k-F_j=H_j. $$
Using the definition of $H_j$,
$$ F_{k+2}-1-F_j=F_{j+2}-1, $$
hence
$$ F_{k+2}=F_j+F_{j+2}=2F_j+F_{j+1}. $$
By Eq. (6),
$$ F_{j+3}=2F_j+F_{j+1}, $$
therefore
$$ F_{k+2}=F_{j+3}. $$
Hence
$$ k+2=j+3, $$
so $j=k-1$. But then
$$ q=F_{k-1}<F_k, $$
while every move from $(H_k,F_k)$ satisfies
$$ q\le 2F_k. $$
The resulting position is
$$ (H_k-F_{k-1},F_{k-1}), $$
and
$$ H_k-F_{k-1} =F_{k+2}-1-F_{k-1} =2F_k+F_{k-1}-1-F_{k-1} =2F_k-1. $$
Since
$$ H_{k-1}=F_{k+1}-1, $$
these are unequal for $k\ge2$. Therefore no move from $(H_k,F_k)$ reaches another position of the form $(H_j,F_j)$. Hence every move from $(H_k,F_k)$ goes to a winning position.
Now consider a position $(N,p)$ not of the form $(H_k,F_k)$. We show that there exists a move to such a position.
Choose $k$ so that
$$ H_k<N\le H_{k+1}. $$
Since
$$ H_{k+1}-H_k =F_{k+3}-1-(F_{k+2}-1) =F_{k+1}, $$
we may write
$$ N=H_k+r, \qquad 1\le r\le F_{k+1}. $$
If
$$ r\le 2p, $$
the player removes $r$ chips, leaving
$$ (H_k,r). $$
If this were not a losing position, then some move from it would reach another $(H_j,F_j)$. By the argument above, the only possible target would be $(H_{k-1},F_{k-1})$, which would require removing
$$ H_k-H_{k-1}=F_k. $$
Therefore $r=F_k$, and so $(H_k,r)=(H_k,F_k)$ is losing.
Now suppose
$$ r>2p. $$
Then
$$ N>H_k+2p. $$
Since
$$ N\le H_{k+1}=H_k+F_{k+1}, $$
we have
$$ 2p<F_{k+1}. $$
Hence
$$ p<F_k. $$
By Exercise 34, every positive integer has a unique Fibonacci representation with nonadjacent indices. Since
$$ F_k\le F_{k+1}-1, $$
the number
$$ F_{k+1}-r $$
has such a representation using only Fibonacci numbers strictly below $F_k$. Therefore
$$ r = F_{k+1} - (F_{i_1}+\cdots+F_{i_t}), $$
where all $i_j\le k-1$ and no two are consecutive.
Using Eq. (6),
$$ F_{k+1} = F_k+F_{k-1}. $$
Repeatedly replacing adjacent Fibonacci numbers by the next Fibonacci number shows that
$$ r\ge F_k. $$
Since $p<F_k$, we obtain
$$ r>p. $$
Therefore the move removing
$$ q=r-F_k $$
chips is legal, because
$$ 1\le q<r\le 2p+q, $$
hence
$$ q\le2p. $$
After removing $q$ chips, the new position becomes
$$ (H_k+F_k,F_k). $$
But
$$ H_k+F_k = F_{k+2}-1+F_k = 2F_k+F_{k+1}-1 = F_{k+3}-1 = H_{k+1}. $$
Hence the new position is
$$ (H_{k+1},F_k). $$
Replacing $k$ by $k-1$, this is of the losing form.
Thus every position not of the form $(H_k,F_k)$ can be moved to one that is, and every position of that form can move only to winning positions. Therefore the losing positions are exactly $(H_k,F_k)$.
We now apply this to the initial position with $1000$ chips. On the first move there is no previous move, so the first player may remove any positive number less than $1000$.
We compute:
$$ F_{16}=987,\qquad F_{17}=1597. $$
Hence
$$ H_{15}=F_{17}-1=1596. $$
This exceeds $1000$. Also,
$$ H_{14}=F_{16}-1=986. $$
Therefore
$$ 986<1000\le1596. $$
The unique losing position in this interval is
$$ (H_{14},F_{14})=(986,377). $$
To leave $986$ chips, the first player must remove
$$ 1000-986=14 $$
chips.
Therefore the optimal first move is to remove $14$ chips.
$$ \boxed{14} $$
Verification
After the first player removes $14$ chips, $986$ chips remain. Since
$$ 986=F_{16}-1, $$
the position is $(H_{14},14)$ with
$$ 14<F_{14}=377. $$
Any legal reply removes at most $28$ chips. The inductive characterization above shows that every move from this position reaches a winning position for the next player.
Conversely, if the first player removes any number other than $14$, the remaining number of chips is not equal to $F_k-1$ for any Fibonacci number $F_k$. Hence the second player can move to a losing position of the form $(H_j,F_j)$ and thereafter maintain the winning strategy.
Notes
The losing positions are generated by the Fibonacci numbers because the admissible move size is controlled by twice the preceding move. This produces the same extremal structure that appears in Zeckendorf representations of Exercise 34.