×

Euclid and Wythoff games. (English) Zbl 1079.91011

In the game Euclid on two positive integers, a move consists of decreasing the larger integer by any positive multiple of the smaller, as long as the result remains positive. The first player unable to move loses. For an integer \(n>0\), the generalized Wythoff game \(GW_n\) on two nonnegative integers, the moves are of two types: (i) decreasing one of the numbers by a positive integer, leaving the result nonnegative; (ii) decreasing one of the numbers by an integer \(k>0\) and the other by an integer \(l>0\), with \(| k-l| <n\). The player unable to move because the position is (0,0) loses. Winning strategies for both have been previously given. In this paper the author gives two characterizations of the Sprague-Grundy function values for Euclid in terms of the winning strategy of \(GW_n\).

MSC:

91A46 Combinatorial games
91A05 2-person games
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] E.R. Berlekamp, J.H. Conway, R.K. Guy, Winning Ways for your Mathematical Plays, vols. 1-4, second ed., vol. 1, 2001, vol. 2, 3, 2003, vol. 4, 2004, A K Peters, Natick, MA, 1982.; E.R. Berlekamp, J.H. Conway, R.K. Guy, Winning Ways for your Mathematical Plays, vols. 1-4, second ed., vol. 1, 2001, vol. 2, 3, 2003, vol. 4, 2004, A K Peters, Natick, MA, 1982. · Zbl 0485.00025
[2] Coxeter, H. S.M., The golden section, phyllotaxis and Wythoff’s game, Scripta Math., 19, 135-143 (1953) · Zbl 0053.00702
[3] Fraenkel, A. S., How to beat your Wythoff games’ opponent on three fronts, Amer. Math. Monthly, 89, 353-361 (1982) · Zbl 0504.90087
[4] Lengyel, T., A Nim-type game and continued fractions, Fibonacci Quart., 41, 310-320 (2003) · Zbl 1046.05500
[5] G. Nivasch, The Sprague-Grundy function of the game Euclid, 2004, Discrete Math., in press.; G. Nivasch, The Sprague-Grundy function of the game Euclid, 2004, Discrete Math., in press. · Zbl 1201.91020
[6] Olds, C. D., Continued Fractions (1963), Random House: Random House New York · Zbl 0123.25804
[7] Wythoff, W. A., A modification of the game of Nim, Nieuw Arch. Wisk., 7, 199-202 (1907)
[8] A.M. Yaglom, 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.; A.M. Yaglom, 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. · Zbl 0147.00102
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.