DIMACS TR: 2005-07
On the misere version of game Euclid and miserable games
Author: Vladimir Gurvich
ABSTRACT
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 integer $x,y \geq 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 $(k F_i , k F_{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 {\em 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 + g^+ $.
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 {\em 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 + g^+ $, where $i$
is the number of non-empty piles, while in all other positions $g^+
\equiv g^-$
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2005/2005-07.ps.gz
DIMACS Home Page