An Algorithm to Solve the Zeckendorf Game

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.