Solution
Fibonacci Nim
Show the problem again
A pile contains 76 stones. Two players alternate. The first player may remove any number of stones except the whole pile (at least 1, at most 75). After that, each player removes at least one stone and at most twice the number of stones the opponent just removed. The player who takes the last stone wins. The first player has exactly one winning first move. How many stones does it remove? Give an integer.
Worked solution
The answer is 21. This is Fibonacci Nim. A pile of size n is lost for the player who must move first (with the first-move cap rule above) exactly when n is a Fibonacci number; in general, the winning strategy is to remove the smallest term of the Zeckendorf representation of the current pile, and then to keep doing so. Here 76 = 55 + 21, so the smallest Zeckendorf term is 21. Removing 21 leaves 55, a Fibonacci number. The opponent's reply of at most 42 stones cannot clear 55, and every reply can be answered so that the pile again becomes a Fibonacci number or the winner takes the final stones. A full search over states (pile, current cap) confirms that 21 is the only winning opening move.
Source: Fibonacci Nim (Michael Whinihan, 1963), a classic Zeckendorf-representation game. Statement written for AxiomIQ.