Every explanation I read on this doesn’t really explain it well. Specifically, I’m talking about the misere variant of the game where the person who reduces the last number to 0 loses.
Suppose I have three rows, with the numbers being 11, 13, and 15 and I go first.
What’s the trick to winning here? And why does it work? Does it matter who goes first or who goes second?
In: 0
There are only two real moves in Nim.
1. Remove all but 1 item from a row. This leaves the row in play for a single subsequent move.
2. Remove a row. This removes the row from play.
Everything else is just passing turn, essentially, because the board state doesn’t change.
We can game this out, using A, B, and C to model the three rows, and A-, B-, and C- when there’s only one item left in the row.
Let’s say you drop A to A- (Option 1).
If they clear a row (Option 2 on, say, B), then you can clear the last row (C) and your opponent is left with the last move on A-. You win.
If they reduce a row (Option 1 on B to B-), then you can reduce C to C-, and there will be three items left (A-, B-, C-). Your opponent takes A-, you take B-, your opponent is left with the last move on C-. You win.
Rewind to the start, and let’s say you clear C (Option 2).
If they clear a row (Option 2 on, say, B again), then you can reduce A to A- and leave them with the last move on A-. You win.
If they reduce a row (Option 1 on B to B-), then you can clear A, leaving them with the last move on B-. You win.
If you start the turn order with three rows of multiple items, you are guaranteed to win if you play using the above rules. If you don’t do either Option 1 or Option 2 and leave all rows with more than 1 item, then your opponent will be in the position you were just in, and they can win if they do either option.
Latest Answers