Nim Game Strategy Formula?

Question

Is there a formula you can use (besides) binary to help figure out a winning strat for a nim game. 
There are 15 objects in one row on a table. Each player can take 1, 2, or 3 objects at a time. The player who takes the last object wins. 

There are 15 objects in one row on a table. Each player can take 1, 2, or 3 objects at a time. The player who takes the last object loses. 

There are 77 objects on the table. Each player can remove 1 to 9 objects from the (single) pile. The player who takes the last object loses.

Any help is very appreciated!

Thomas the Mathemagician · Accepted Answer

In the first variation, if there are 4 pieces remaining and it's your pick, you can't possibly win; whatever you take will leave enough for your opponent to take the rest.  If there are 5 pieces, then you pick one and leave the "4 problem" for him.  Extending this upward, if you leave 8, then the sum of pieces that you and he take must equal 4 to ensure victory.  Therefore, your strategy is to leave 4n pieces, where n is an integer.  Elect to go first and take 3 and the game is decided.

In the opposite scenario, you want to pick from 4; you leave 1 and he curses under his breath.  You want to leave 5 pieces so he has no choice.  Since you can guarantee picking 4 pieces between the both of you, you want to leave 4n + 1; elect to go first again and take 2 so you can force the pile down to 13, then 9, then 5, then civil war...

The last scenario is like the second one, but you want to leave 11 and guarantee 10 pieces between yourselves each pair of moves, which means 10n + 1; go first and take 6, then take the 10's complement of your opponent when it's your turn.

Trending News

Nim Game Strategy Formula?

1 Answer