부산대학교 도서관

Summary: ``Zeckendorf proved that every positive integer $n$ can be written uniquely as the sum of nonadjacent Fibonacci numbers. We use this decomposition to construct a two-player game. Given a fixed integer $n$ and an initial decomposition of $n = nF_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; depending on the choice of moves, the length of the game and the winner can vary, although for $n \geq 2$ there is a nonconstructive proof that Player 2 has a winning strategy. \par ``Initially, the lower bound of the length of a game was order $n$ (and known to be sharp), whereas the upper bound was of size $n \log n$. Recent work decreased the upper bound to size $n$, but with a larger constant than was conjectured. We improve the upper bound and obtain the sharp bound of $\frac{\sqrt 5+3}{2}n - IZ(n) - \frac{1+\sqrt 5}{2} Z(n)$, which is of order $n$ as $Z(n)$ is the number of terms in the Zeckendorf decomposition of $n$ and $IZ(n)$ is the sum of indices in the Zeckendorf decomposition of $n$ (which are at most of sizes $\log n$ and $\log^2 n$, respectively). We also introduce a greedy algorithm that realizes the upper bound, and show that the longest game on any $n$ is achieved by applying splitting moves whenever possible.''