An Algorithm to Solve the Zeckendorf Game

Authors

  • William Li Delbarton School
  • Robert Bitler mentor, Delbarton School

DOI:

https://doi.org/10.47611/jsrhs.v10i3.1641

Keywords:

Zeckendorf Game, Zeckendorf Theorem, Fibonacci sequence

Abstract

Zeckendorf proved that every positive integer N can be written uniquely as the sum of non-adjacent Fibonacci numbers. This property can be used to create a two-player Zeckendorf game. A recent paper proved that player 2 has the winning strategy for all N>2. However, the proof was non-constructive. In fact, the paper only provided computer code of the winning strategy of player 2 by brute force. In this paper, we present an algorithm to efficiently solve the Zeckendorf game. Specifically, we convert the game to a directed graph, prove that the graph has no cycles and only one terminal node, and construct an iterative algorithm to find all the winning strategies of player 2. We provide an example to show that the proposed algorithm works much more efficiently than a brute force approach.

Downloads

Download data is not yet available.

References or Bibliography

Zeckendorf, E. (1972), Représentation des nombres naturels par une somme des nombres de Fibonacci ou de nombres de Lucas, Bulletin de la Société Royale des Sciences de Liège 41, pages 179–182.

Baird-Smith P., Epstein A., Flint K., Miller S.J. (2020). The Zeckendorf Game. In: Nathanson M. (eds) Combinatorial and Additive Number Theory III. CANT 2018. Springer Proceedings in Mathematics & Statistics, vol 297. Springer, Cham. https://doi.org/10.1007/978-3-030-31106-3_3.

Li R., Li X., Miller S.J., Mizgerd C., Sun C., Xia D., Zhou Z., (2020). Deterministic Zeckendorf Games. arXiv eprint 2006.16457, https://arxiv.org/abs/2006.16457.

Baird-Smith P., Epstein A., Flint K., Miller S.J. (2018). The Generalized Zeckendorf Games. arXiv eprint 1809.04883, https://arxiv.org/abs/1809.04883.

Published

10-10-2021

How to Cite

Li, W., & Bitler, R. (2021). An Algorithm to Solve the Zeckendorf Game. Journal of Student Research, 10(3). https://doi.org/10.47611/jsrhs.v10i3.1641

Issue

Section

HS Research Projects