Misere Nim with piles of 1, 1, 1 and 5, where the player who takes the last object loses. Who wins with correct play, what is the winning first move, and how does it differ from the normal play answer?

Misere Nim with piles of 1, 1, 1 and 5, where the player who takes the last object loses. Who wins with correct play, what is the winning first move, and how does it differ from the normal play answer?

Approach: Work out who loses in a position made only of piles of size one, then decide what the player who empties the last big pile should leave behind.

The first player wins by removing the entire pile of 5, leaving three singleton piles. When every pile has size 1 the moves are forced, so the parity of the number of piles decides it: the player to move loses exactly when that number is odd, since he takes one and the count alternates down to the last object being his. Leaving three singletons therefore hands the loss to the opponent. The general misere rule is to follow the ordinary XOR strategy while some pile still has at least 2 objects, and when the last such pile is cleared, leave an odd number of singletons. Normal play answers differently here: the nim sum of 1, 1, 1 and 5 is 4, so the normal winning move cuts the 5 down to 1, which in misere play leaves four singletons and loses.

Follow-up: In misere Nim with piles 2, 3 and 7, what is the winning first move?

Key concepts: misere play, nim sum, singleton piles, parity of piles.