Annals of Combinatorics 2 (1998) 197-210
Heap Games, Numeration Systems and Sequences
Aviezri S. Fraenkel
Department of Applied Mathematics and Computer Science, Weizmann Institute
of Science, Rehovot 76100, Israel
Received June 3, 1998
AMS Subject Classification: 90D46, 05A99
Abstract. We propose and analyze a 2-parameter family of 2-player games on two heaps of tokens, and present a strategy based on a class of sequences. The strategy looks easy, but it is actually hard. A class of exotic numeration systems is then used, which enables us to decide whether the family has an efficient strategy or not. We introduce yet another class of sequences and demonstrate its equivalence with the class of sequences defined for the strategy of our games.
Keywords: heap games, numeration systems, sequences
1. E.R. Berlekamp, J.H. Conway, and R.K. Guy, Winning Ways (two volumes), Academic Press, London, (1982).
2. M. Boshernitzan and A.S. Fraenkel, Nonhomogeneous spectra of numbers, Discr. Math. 34 (1981) 325–27.
3. M. Boshernitzan and A.S. Fraenkel, A linear algorithm for nonhomogeneous spectra of numbers, J. of Algorithms 5 (1984) 187–198.
4. J.H. Conway, On Numbers and Games, Academic Press, London, (1976).
5. H.S.M. Coxeter, The golden section, phyllotaxis and Wythoff's game, Scripta Math., 19 (1953) 135–143.
6. A.S. Fraenkel, How to beat your Wythoff games' opponents on three fronts, Amer. Math. Monthly, 89 (1982) 353–361.
7. A.S. Fraenkel, Systems of numeration, Amer. Math. Monthly, 92 (1985) 105–114.
8. A. Gangolli and T. Plambeck, A note on periodicity in some octal games, Internat. J. Game Theory, 18 (1989) 311–320.
9. R.L. Graham, S. Lin and C.-S. Lin, Spectra of numbers, Math. Mag., 51 (1978) 174–176.
10. R.K. Guy and C.A.B. Smith, The G-values of various games, Proc. Camb. Phil. Soc., 52 (1956) 514–526.
11. T.J. Schaefer, On the complexity of some two-person perfect-in-for-ma-tion games, J. Comput. System Sci., 16 (1978) 185–225.
12. N.J.A. Sloane, Sloane's On-Line Encyclopedia of Integer Sequences, http://www.research.att.com/\~njas/sequences, (1998)
13. W.A. Wythoff, A modification of the game of Nim, Nieuw Arch. Wisk., 7 (1907) 199–202.
14. A.M. Yaglom and I.M. Yaglom, Challenging Mathematical Problems with Elementary Solutions, translated by J. McCawley, Jr., revised and edited by B. Gordon, Vol. II, Holden-Day, San Francisco, (1976).
15. E. Zeckendorf, Reprèsentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. Roy. Sci. Liège, 41 (1972) 179–182.