Advanced Search

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

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Article Journal Journal Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]