<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume8 Issue2" %>
On Fraenkel's N-Heap Wythoff's Conjectures
Xinyu Sun1 and Doron Zeilberger2
1Department of Mathematics, Temple University, Philadelphia, PA 19122, USA
2Department of Mathematics, Rutgers University, Piscataway, NJ 08854, USA
Annals of Combinatorics 8 (2) p.225-238 June, 2004
AMS Subject Classification: 91A46, 68R05
The N-heap Wythoff's game is a two-player impartial game with N piles of tokens of sizes . Players take turns removing any number of tokens from a single pile, or removing (a1,..., aN) from all piles --- ai tokens from the i-th pile, providing that and where is the nim addition. The first player that cannot make a move loses. Denote all the P-positions (i.e., losing positions) by and for all . Two conjectures were proposed on the game by Fraenkel [7]. When are fixed, i) there exists an integer N1 such that when ii) there exist integers N2 and such that when and , where , and the golden section.
In this paper, we provide a sufficient condition for the conjectures to hold, and subsequently prove them for the three-heap Wythoff's game with the first piles having up to 10 tokens.
Keywords: Wythoff's game, combinatorial game


1. U. Blass and A.S. Fraenkel, The Sprague-Grundy function for Wythoff's game, Theoret. Comp. Sci. 75 (1990) 311--333.

2. U. Blass, A.S. Fraenkel, and R. Guelman, How far can nim in disguise be stretched?, J. Combin. Theory, Ser. A 84 (1998) 145--156.

3. E.R. Berlekamp, J.H. Conway, and R.K. Guy, Winning Ways for Your Mathematical Plays, Vols. I & II, Academic Press, London, 1982, 2nd Ed., A.K. Peters, Natick, MA, 2001.

4. H.S.M. Coxeter, The golden section, phyllotaxis and Wythoff's game, Scripta Math. 19 (1953) 135--143.

5. A. Dress, A. Flammenkamp, and N. Pink, Additive periodicity of the Sprague-Grundy function of certain Nim games, Adv. Appl. Math. 22 (1999) 249--270.

6. A.S. Fraenkel, How to beat your Wythoff games' opponent on three fronts, Amer. Math. Monthly 89 (1982) 353--361.

7. A.S. Fraenkel, Complexity, appeal and challenges of combinatorial games, Theoret. Comput. Sci., to appear.

8. A.S. Fraenkel and I. Borosh, A generalization of Wythoff's game, J. Combin. Theory, Ser. A 15 (1973) 175--191.

9. A.S. Fraenkel and M. Ozery, Adjoining toWythoff's game its P-positions as moves, Theoret. Comput. Sci. 205 (1998) 283--296.

10. A.S. Fraenkel and D. Zusman, A new heap game, Theoret. Comput. Sci. 252 (2001) 5--12.

11. R.K. Guy and R.J. Nowakowski, Unsolved problems in combinatorial games, In: More Games of No Chance, Cambridge University Press, Cambridge, 2002, pp. 457--473.

12. H. Landman, A simple FSM-based proof of the additive periodicity of the Sprague-Grundy function of Wythoff's game, In: More Games of No Chance, Cambridge University Press, Cambridge, 2002, pp. 383--386.

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, Vol. II, Holden-Day, San Francisco, translated by J. McCawley Jr., revised and edited by B. Gordon, 1967.