부산대학교 도서관

Summary: ``Zeckendorf proved that every positive integer $n$ can bewritten uniquely as the sum of nonadjacent Fibonacci numbers. We usethis decomposition to construct a two-player game. Given a fixedinteger $n$ and an initial decomposition of $n = nF_1$, the two playersalternate by using moves related to the recurrence relation $F_{n+1} =F_n + F_{n-1}$, and whoever moves last wins. The game always terminatesin the Zeckendorf decomposition; depending on the choice of moves, thelength 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 \logn$. Recent work decreased the upper bound to size $n$, but with alarger constant than was conjectured. We improve the upper bound andobtain the sharp bound of $\frac{\sqrt 5+3}{2}n - IZ(n) - \frac{1+\sqrt5}{2} Z(n)$, which is of order $n$ as $Z(n)$ is the number of terms inthe Zeckendorf decomposition of $n$ and $IZ(n)$ is the sum of indicesin the Zeckendorf decomposition of $n$ (which are at most of sizes$\log n$ and $\log^2 n$, respectively). We also introduce a greedyalgorithm that realizes the upper bound, and show that the longest gameon any $n$ is achieved by applying splitting moves whenever possible.''