  Zeckendorf proved that every positive integer $n$ can be written uniquely as
the sum of non-adjacent Fibonacci numbers. We use this to create a two-player
game. Given a fixed integer $n$ and an initial decomposition of $n = n F_1$,
the two players alternate by using moves related to the recurrence relation
$F_{n+1} = F_n + F_{n-1}$, and whoever moves last wins. The game always
terminates in the Zeckendorf decomposition, though depending on the choice of
moves the length of the game and the winner can vary. We find upper and lower
bounds on the number of moves possible. The upper bound is on the order of
$n\log n$, and the lower bound is sharp at $n-Z(n)$ moves, where $Z(n)$ is the
number of terms in the Zeckendorf decomposition of $n$. Notably, Player 2 has
the winning strategy for all $n > 2$; interestingly, however, the proof is
non-constructive.

Number Theory;Combinatorics