Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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. 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 is played as a misere game. Probably the analysis is similar to normal-play Nim with some modification.

Recently there was a theory of Misere quotients where each game has a commutative monoid assoicated with it. What does that monoid looks like here? Is it finitely generated?

share|improve this question
2  
The winning positions in misère Nim are the same for for normal play (pointwise xor of the sizes in binary is nonzero), except when there are only heaps of size 1 left, in which case it’s reversed (i.e., even number of heaps is winning). –  Emil Jeřábek Aug 1 '11 at 15:36
1  
In particular, (3,4,1) is a first player win, whereas (4,5,1) is a second player win, so your friend or you got it wrong. –  Emil Jeřábek Aug 1 '11 at 15:48

1 Answer 1

up vote 7 down vote accepted

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$.)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.