On Fraenkel's N-Heap Wythoff's Conjectures

Xinyu Sun^{1} and Doron Zeilberger^{2}

xysun@math.temple.edu

zeilberg@math.rutgers.edu

Annals of Combinatorics 8 (2) p.225-238 June, 2004

Abstract:

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 (*a*_{1},..., *a*_{N})
from all piles --- *a*_{i} 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 *N*_{1} such that when
ii) there exist integers *N*_{2} 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.

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.

References:

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.