Wythoff's Game is an impartial game consisting of two piles of tokens. Players are to remove any number of tokens from a single pile, or the same number of tokens from both piles. The first player that cannot make a move loses. The P-positions are well know and well explained by Fraenkel: they are two sequences of numbers An and Bn, n > = 0, such that An = mex{Am, Bm | 0 <= m < n} and Bn = An + n with A0 = B0 = 0. They can also be written as An = floor(nP) and Bn = floor(nP) + n, where P = (1+sqrt(5))/2 (the golden section), and floor(x) is the greatest integer in x. Various generalizations and results of the game can be found as listed in the references.

Another generalization of the game involving more than two piles was discussed by Fraenkel and Guy: given N piles of tokens, whose sizes are A1, ..., AN, A1 <= ... < = AN. A player can remove any number of tokens from a single pile, or remove (a1, ..., aN) tokens from all piles --- ai tokens from the i-th pile, providing that 0 < = ai <= Ai, sumi=1N (ai) > 0, and a1 \oplus ... \oplus aN = 0, where \oplus is the nim addition. Denote all the P-Positions by (A1, ..., AN-2, AN-1n, ANn), AN-2 <= AN-1n <= ANn and AN-1n < AN-1n+1 for all n > = 0. Two conjectures were presented on the game: when A1, ..., AN-2 are fixed, i) there exists an integer N1 such that when n > N1, ANn = AN-1n + n. ii) there exists integers N2 and M2 such that when n > N2, AN-1n = floor(nP) + en + M2 and ANn = AN-1n + n, where P = (1+sqrt(5))/2 and -1 < = en < = 1. It is obvious that in the conjectures, AN-1n = mex(AN-1i, ANi: 0 <= i < n} union T), where T is a (small) set of integers.

On Fraenkel's N-Heap Wythoff's Conjectures

Xinyu Sun and Doron Zeilberger

(To appear in Annals of Combinatorics)

The paper proves both of the conjectures for three-heap Wythoff's game when the first heap has up to 10 tokens. It is available in tex, pdf (201KB), dvi, and ps (853KB) formats. Here is the associated eps (485KB) file. The Maple package is also available.

The following table lists the results in the paper. Click here for the complete result. In the file, each position is represented the same way as in the paper: [a, b, c] is a position having a tokens in the first pile, a + b second and a + b + c third.

m Tm Sm  am  N1m N2m 0     0 1 1 1 1 2, 17, 22 -4 21 28 2   1, 5, 8, 24, 26, 32 -10 28 58 3 1, 2, 3 2, 3, 4, 5, 8, 10, 11, 12, 28, 41, 57 -16 48 73 4 3, 6 2, 5, 6, 7, 8, 9, 11, 12, 14, 17, 46, 48, 59 -20 126 208 5 4, 7, 10 1, 3, 5, 6, 8, 10, 11, 12, 15, 16, 17, 18, 19, 28, 56, 77, 83 -26 71 123 6 2, 3, 4, 6 1, 2, 3, 4, 5, 7, 8, 10, 11, 12, 13, 14, 15, 16, 18, 21, 44, 58, 95, 96, 132 -32 113 232 7 1, 4, 6, 7, 9 0, 1, 2, 4, 5, 6, 7, 8, 10, 12, 13, 14, 15, 17, 18, 19, 21, 22, 23, 24, 28, 30, 86, 88, 232, 251 -39 227 343 8 3, 5, 10, 13 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 13, 14, 16, 17, 19, 20, 21, 22, 24, 26, 27, 28, 33, 34, 46, 155, 257, 390, 415 -46 388 648 9 6, 4, 11, 15 0, 1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 19, 20, 24, 25, 26, 27, 30, 36, 37, 44, 48, 62, 254, 388, 421, 676 -52 645 645 10 6, 7, 8, 9, 13 0, 1, 2, 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 25, 27, 28, 29, 30, 31, 32, 34, 39, 50, 53, 103, 391, 424, 690 -56 656 656

Wythoff's Sequence and N-Heap Wythoff's Conjectures

Xinyu Sun

(submitted)

As in the previous paper, define a Wythoff's sequence as a sequence of pairs of integers {(An, Bn)} n > = n0 , if there exist a finite set of integers T such that An = mex({Ai, Bi : n0 <= i < n} union T), Bn = An + n, and the intersection of {Bn} and T is empty.

In the paper, a series of properties of Wythoff's sequence are proved. For example, it proves the relationships between the two series of integers A and B; provides ways to calculate the series without using the definition, i.e., mex; and as a corollary, proves the two conjectures on N-heap Wythoff's game are equivalent. It also proved that the value of M2 in the second conjecture can be found relatively easily.

The paper is available in tex, pdf, dvi, and ps formats.

References

U. Blass and A. S. Fraenkel, The Sprague-Grundy function for Wythoff's game, Theoret. Comp. Sci. 75 (1990) 311-333. E. R. Berlekamp, J. H. Conway and R. K. Guy, Winning Ways for your Mathematical Plays, Academic Press, London, 1982. H. S. M. Coxeter, The golden section, phyllotaxis and Wythoff's game, Scripta Math. 19 (1953) 135-143. A. Dress, A. Flammenkamp and N. Pink, Additive periodicity of the Sprague-Grundy function of certain Nim games, Adv. in Appl. Math. 22 (1999) 249-270. A. S. Fraenkel, How to beat your Wythoff games' opponent on three fronts, Amer. Math. Monthly 89 (1982) 353-361. A. S. Fraenkel, Complexity, Appeal and challenges of combinatorial games, preprint. A. S. Fraenkel and I. Borosh, A generalization of Wythoff's game, J. Combin. Theory (Ser. A) 15 (1973) 175-191. A. S. Fraenkel and M. Ozery, Adjoining to Wythoff's game its P-Positions as moves, Theoret. Comput. Sci. 205 (1998) 283-296. A. S. Fraenkel and D. Zusman, A new heap game, Theoret. Comput. Sci. 252 (2001) 5-12. R. K. Guy and R. J. Nowakowski, Unsolved problems in combinatorial games, in: More Games of No Chance, Cambridge University Press, Cambridge, 2002, 457-473. 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, 383-386. W. A. Wythoff, A modification of the game of Nim, Nieuw Arch. Wisk. 7 (1907) 199-202. A. M. Yaglom and I. M. Yaglom, Challenging mathematical problems with elementary solutions, Vol.II, Holden-Day, San Francisco, 1967.