Euclid, Calkin & Wilf — playing with rationals. (English) Zbl 1193.91033

Summary (translated from the German): The combinatorial game Euclid was introduced by A. J. Cole and A. J. T. Davie [Math. Gaz. 53, 354–357 (1969; Zbl 0186.25303)]. Two players take turns drawing from a position \((a, b)\in\mathbb N^2\), where the drawing player has to subtract a multiple of the smaller number from the larger number. The player making the move has to subtract a multiple of the smaller number from the larger number, so that the result is still in \(\mathbb N^2\). The first player who can no longer move has lost. Up to now, we know elementary (Cole & Davie), geometrical (Lengyel) and number (Lengyel) and number-theoretic (Schwartz) descriptions of the winning positions for Euclid (optimal play of both players is assumed).
The authors add a graph-theoretic winning strategy by relating Euclid to the Calkin-Wilf. This remarkable tree, introduced by N. J. Calkin and {it H. S. Wilf} [Am. Math. Mon. 107, No. 4, 360–363 (2000; Zbl 0983.11009)], generates all positive rational numbers in abbreviated form by a simple rule exactly once.


91A46 Combinatorial games
91A43 Games involving graphs
11B75 Other combinatorial number theory
05C05 Trees


Full Text: DOI Link


[1] Alkauskas, G.; Steuding, J.: Statistical properties of the Calkin-Wilf tree and applications to finite contin- ued fractions. Preprint.
[2] Bird, R.; Gibbons, J.; Lester, D.: Functional pearl: enumerating the rationals. J. Funct. Programming 16 (2006), 281-291. 117 · Zbl 1103.68444 · doi:10.1017/S0956796806005880
[3] Bradley, D.M.: Counting the Positive Rationals: A Brief Survey. Preprint available at http://germain.umemat.maine.edu/faculty/bradley/papers/pub.html
[4] Calkin, N.; Wilf, H.: Recounting the rationals. Amer. Math. Monthly 107 (2000), 360-363. · Zbl 0983.11009 · doi:10.2307/2589182
[5] Cole, A.J.; Davie, A.J.T.: A game based on the Euclidean algorithm and a winning strategy for it. Math. Gaz. 53 (1969), 354-357. · Zbl 0186.25303 · doi:10.2307/3612461
[6] Lehmer, D.H.: On Stern’s diatomic series. Amer. Math. Monthly 36 (1929), 59-67.
[7] Lengyel, T.: A nim-type game and continued fractions. Fibonacci Quart. 41 (2003), 310-320. · Zbl 1046.05500
[8] Lengyel, T.: On calculating the Sprague-Grundy function for the game Euclid . Proceedings of the 11th International Conference on Fibonacci Numbers and Their Applications 2004, 169-175 (to appear).
[9] Newman, M.: Recounting the rationals, Continued. Credited in Amer. Math. Monthly 110 (2003), 642-643.
[10] Reznick, B.: Regularity properties of the Stern enumeration of the rationals. Preprint available at http://de.arxiv.org/pdf/math.NT/0610601.pdf?front · Zbl 1204.11027
[11] Sloane, N.; Plouffe, S.: The On-line Encyclopedia of integer sequences . http://www.research.att.com/\sim njas/sequences/ · Zbl 0845.11001
[12] Stern, M.A.: Über eine zahlentheoretische Funktion. J. Reine Angew. Math. 55 (1858), 193-220.
[13] Steuding, J.: Diophantine Analysis . CRC Press/Chapman-Hall 2005. · Zbl 1101.11022
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.