Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 1108.91019
Gurvich, Vladimir A.
On the misere version of game Euclid and miserable games. (English)
[J] Discrete Math. 307, No. 9-10, 1199-1204 (2007). ISSN 0012-365X

Summary: Recently, Gabriel Nivasch got the following remarkable formula for the Sprague-Grundy function of game Euclid: $g^+(x,y)=\lfloor |x/y-y/x| \rfloor$ for all integers $x$, $y\ge 1$. We consider the corresponding misere game and show that its Sprague-Grundy function $g^-(x,y)$ is equal to $g^+(x,y)$ for all positions $(x,y)$, except for the case when $(x,y)$ or $(y,x)$ equals $(kF_i,kF_{i+1})$, where $F_i$ is the $i$th Fibonacci number and $k$ is a positive integer. It is easy to see that these exceptional Fibonacci positions are exactly those in which all further moves in the game are forced (unique) and hence, the results of the normal and misere versions are opposite; in other words, for these positions $g^+$ and $g^-$ take values 0 and 1 so that $g^-=1-g^+=(-1)^{i+1}+ g^+$. \par Let us note that the good old game of Nim has similar property: if there is at most one bean in each pile then all further moves are forced. Hence, in these forced positions the results of the normal and misere versions are opposite, while for all other positions they are the same, as it was proved by Charles Bouton in 1901. Respectively, in the forced positions $g^+$ and $g^-$ take values 0 and 1 so that $g^-=1-g^+=(-1)^{i+1}+g^+$, where $i$ is the number of non-empty piles, while in all other positions $g^+\equiv g^-$.

MSC 2000:: *91A46 Combinatorial games

Keywords: combinatorial games; impartial games; misere; Nim; Wythoff's game; game Euclid; Sprague-Grundy function

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article 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]