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.


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


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?

  • 3
    $\begingroup$ 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). $\endgroup$ Commented Aug 1, 2011 at 15:36
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Aug 1, 2011 at 15:48

1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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