Welcome to NRICH.

 
Nim's Game
By Jeff on Monday, February 7, 2000 - 12:59 am:

Can anyone explain the way one can consistently win at Nim's game? I can't work it out and I am sure that there must be a formula to apply to the game.

(The game involves two players and twelve counters. These counters are placed in three rows on the table: one row of 5, one row of 4 and one row of 3. Players take turns to remove any number of counters from any single row. The winner is the person who leaves one remaining counter on the table).

Many thanks.

By Anonymous on Friday, February 11, 2000 - 01:01 am:

The brute force way is to make up lists of winning and losing positions. Any position one move away from any losing position is a winning position. Any position which can only move to a winning position is a losing position.

You will find that 001 022 033 044 111 123 and 145 (+rearrangements) are losing positions. Since you can get to 145 from the starting position 345 in one move, the first player can always win. The winning strategy is simply to always leave your opponent in a losing position (starting by taking two stones away from the first pile).