My friend likes to impress people by playing 3-5-7 which has three piles of counters of sizes 3, 5 and 7. You can remove any number of coins from a single pile, the last player to move loses.


ooo  

ooooo  

ooooooo


This is a winning position for the first player, but With a solid understanding of the game tree she wins nearly every time playing second. She says, it reduces to knowing a few winning positions.


Two piles of the same size is second player win, in the jargon of [Combinatorial Game Theory](http://lessonsinplay.heartofthetree.ca/). Here is the pile (5,5). 


ooooo  

ooooo


If first player moves to (5,n) for n > 1, second player can imitate on the other pile, moving to (n,n). However, if first player moves to (5,1), second player moves to 1 and wins.


The other winning positions she remembers is (3,4,1) and (4,5,1). She can win once she recognizes these positions. Eventually (after losing many times) I told her that (n, n+1,1) is a losing position for any n...




---


If our game were played in normal play convention (player moving last **wins**), but real life [Nim](http://en.wikipedia.org/wiki/Nim) is played as a [misere](http://miseregames.org/) game. Probably the analysis is similar to normal-play Nim with some modification. 


Recently there was a theory of [Misere quotients](http://arxiv.org/abs/math.CO/0612616) where each game has a commutative monoid assoicated with it. What does that monoid looks like here? Is it finitely generated?



Analysis of Misere Nim?
Let $\oplus$ denote the bitwise xor operation on natural numbers. It is both well-known and easy to verify that a Nim position $(n\_1,\dots,n\_k)$ is a second player win in misère Nim if and only if some $n\_i>1$ and $n\_1\oplus\cdots\oplus n\_k=0$, or all $n\_i\le1$ and $n\_1\oplus\cdots\oplus n\_k=1$.


If I understand it correctly, this translates to the following structure. Let $A=(\omega,\oplus,0)$ (in other words, $A$ is the direct sum of countably many copies of the two-element abelian group), let $A\_0=\{0,1\}$ be its submonoid, and let $B=(\{0,1\},\lor,0)$ be the two-element semilattice. Then the underlying monoid of the misère quotient of Nim is the submonoid $Q=(A\times\{1\})\cup(A\_0\times\{0\})$ of the product monoid $A\times B$, the misère quotient itself being $(Q,\{(0,1),(1,0)\})$. If $(n\_1,\dots,n\_k)$ is a Nim position, its value in $Q$ is $(n\_1\oplus\cdots\oplus n\_k,u)$, where $u=0$ if $n\_i\in\{0,1\}$ for each $i$, and $u=1$ otherwise. $Q$ has (as a commutative monoid) the infinite presentation $\langle \{a\_n:n\in\omega\},b\mid a\_n+a\_n=b+b=0,a\_n+b=a\_n+a\_0\rangle$. Finitely generated submonoids of $Q$ are finite, hence $Q$ itself is not finitely generated.


(Note that the monoid corresponding to normal play Nim is just $A$.)


