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 1108.91019
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

Highlights
Master Server