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
fraenkel@wisdom.weizmann.ac.il, http://www.wisdom.weizmann.ac.il/~fraenkel

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


References

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.


Get the LaTex | DVI | PS file of this abstract.

back