Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

Query:
Fill in the form and click »Search«...
Format:
Display: entries per page entries
Zbl 1193.91033
Hofmann, Stefanie; Schuster, Gertraud; Steuding, Jörn
Euclid, Calkin \& Wilf --- playing with rationals.
(English)
[J] Elem. Math. 63, No. 3, 109-117 (2008). ISSN 0013-6018; ISSN 1420-8962/e

{\it A. J. Cole} and {\it A. J. T. Davie} [A game based on the Euclidean algorithm and a winning strategy for it'', Math. Gaz. 53, 354--357 (1969; Zbl 0186.25303)] introduced and analyzed a combinatorial game based on the Euclidean algorithm. In this game, Euclid, a position is a pair of positive integers $(a,b)$. The two players alternate moves, where a move consists of decreasing the larger number of $a$ or $b$ by any positive multiple of the smaller of the two numbers, as long as the result remains positive. The first player who cannot move loses the game. {\it N. J. Calkin} and {it H. S. Wilf} [Recounting the rationals'', Am. Math. Mon. 107, No.\,4, 360--363 (2000; Zbl 0983.11009)] used a tree to construct a one-to-one function from the positive integers to the positive rational numbers. In the paper under review, the authors characterize winning positions in Euclid according to the location of the rational number $\frac{a}{b}$ in the Calkin-Wilf tree. Using depths in the Calkin-Wilf tree to define a distribution over positions, the authors prove that the first player wins with approximately $\frac{2}{3}$ probability. Further, the authors summarize and provide references to past work on Euclid and other approaches to listing the positive rational numbers. [Reviewd by Michael A. Jones (MR 2009e:91046)]
MSC 2000:
*91A46 Combinatorial games
91A43 Games involving graphs
11B75 Combinatorial number theory
05C05 Trees

Keywords: Calkin Wilf tree; game Euclid; winning strategy; continued fractions; playing Euclid on the Calkin Wilf tree

Citations: Zbl 0186.25303; Zbl 0983.11009

Highlights
Master Server