Euclid, Calkin \& Wilf --- playing with rationals (Q942848): Difference between revisions

Summary (translated from the German): The combinatorial game Euclid was introduced by \textit{A. J. Cole} and \textit{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 \textit{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.