Thread by @pgeerkens

@GWOMaths The game Nim is played by two players alternately removing items from several piles of items. Absent physical materials, with pen and paper a game can be setup as rows of vertical lines, players stroking them out to "remove" them.

@GWOMaths Each turn a player removes 1 or more items from precisely one pile, or row.

The winner is the player who does not (or, as a variant, does) remove the last item.

Consider the setup of two piles of 2 items:

xx
xx

The player to move can be forced to lose by his opponent.

@GWOMaths Note that this is true in both variants.

a) Last item loses:
-Remove one item and your opponent takes both items from the other pile;
- Take both items from one pile and your opponent removes just one from the other.

b) Last item wins:
Your opponent wins by mirroring your move.

@GWOMaths The position of 2 and 2 is termed a "safe position", as whichever player leaves it can guarantee himself a win.

Whether a particular start position is a guaranteed win (w/ best play) for the 1st of 2nd player is a function of whether the start position is a safe or unsafe one.

@GWOMaths The "Nim sum" is the means of calculating whether a position is safe or unsafe.

It is the positional sum in base 10 of the binary representation of the contents of each pile.

So

xxx
xx
x

has Nim sum of

11
10
01
---
22

This is a safe position as all final digits are even.

@GWOMaths The traditional start for a short game is

xxxxxxx
xxxxx
xxx

which has Nim Sum of

111
101
011
----
223

indicating an unsafe position.

First player can force a win by removing a single item from any row, to set the Nim sum as 222.

@GWOMaths This is a particularly fiendish game for a baby sitter to play with a bright 8 or 9 year old.

I know - I was said 8 or 9 year old.

Before internet Martin Gardner's "Mathematical Puzzles and Diversions" was the holy grail on the game.
amazon.ca/Scientific-Ame…

@GWOMaths For today's puzzle, the (traditional) Nim sum is

01101 = 13
10001 = 17
10111 = 23
11101 = 29
-------------
32314

This is an unsafe position - but despite the apparent complexity can be made safe in a single move, by removing 22 (ie 10110) items from either the 3rd pile.

@GWOMaths It is true in general that every unsafe Nim position can be rendered safe in a single move; and by definition any move from a safe position will leave an unsafe position.

01101 = 13
10001 = 17
00001 = 01
11101 = 29
-------------
22204

@GWOMaths @threadreaderapp unroll

@GWOMaths However, that solution is not unique. A safe position can also be generated by removing 18 items from the 4th pile. This converts the "4" in that pile into a "2", as illustrated here.

01101 = 13
10001 = 17
10111 = 23
01011 = 11 = 29-18
-------------
22224

@GWOMaths Likewise by removing ten items from the 2nd pile.

01101 = 13
00111 = 07 = 17 - 10
10111 = 23
11101 = 29
-------------
22224

These latter two examples better illustrate the means by which **any** unsafe position can be rendered safe in a single move.

@GWOMaths Further, removing 22 items from the 4th pile instead of the 3rd is a losing move, leaving an unsafe rather than safe position. It is faulty thinking that the number of items, alone, is a magical answer.

01101 = 13
10001 = 17
10111 = 23
00111 = 07 = 29 - 22
-------------
21324

@GWOMaths The only pile where there is no safe move available is the first, which has insufficient items to balance the odd number of "16's" contributed from the other three.

01101 = 13
10001 = 17
10111 = 23
11101 = 29
-------------
32314

@GWOMaths The strategy as given works right to game conclusion for the variant "taking last item wins". However there are cusp positions for the variant "taking last item loses" where the winning strategy varies.

We have seen one of these already:

xx
xx

@GWOMaths As a practical guide: having left a safe position with only two piles holding 2 or more items, then when playing "taking last item loses" one must henceforth move based on simple parity.

E.G.

xxx
xx
x

or

xxxxx
xxxx
x
x
x
x
x

are both safe but dangerous.