pen and paper game

hey you probably know this game where you have 3 rows of dots. in first row there are 3 dots, in second row 7 dots and last row 11 dots. now when its your turn you may erase 1 or 2 or 3 or ... up to all points of a single row, but you may only erase in one row per turn. then its your opponents turn. whoever erases the last dot will lose the game.
i kept wondering if there is a simple strategy to always win this game (probably depending on who starts). any ideas?

This is an impartial game (one in which the possible moves are the same for each player in any position) and is the Misère-Form (last player to play loses rather than the normal version which is player who can't play loses). It is called Nim.

To win at the normal version of Nim make a move so that the Nim-sum of the piles is zero. To find the Nim-sum convert each pile size to binary and then add without carrying (bitwise x-or). If the Nim-sum is zero before you make a move then you cannot win against good play. If the Nim-sum is not zero then there is always a move that makes it zero.

For example, piles of 1,3 and 5. In binary 1, 11, 101. The Nim-sum is therefore 101 (align the numbers as if doing long addition and if there are an even number of 1's in a column the result will be zero in that place. Repeat for all columns). Now as the Nim-sum is not zero a move exists that will make it zero. A quick check reveals that one such move is remove 3 from the pile of 5. Check the Nim-sum yourself.
Therefore in this starting configuration the first player wins the normal version.

Your starting configuration does not have a zero Nim-sum (1111) and is therefore won by the first player under normal win rules. This however does not mean that the first player will lose the Misère-Form.

The theory for the Misère-Form is exactly the same except when the Nim-sum check indicates that the player should play to piles of 1,1,0 he should instead play to 1,0,0 or 1,1,1. This is a simple adjustment. Therefore as the game must pass through this point the first player will still win the game against all opposing moves.

This concludes XanthosNZ's crash course of game theory. Tip your servers.

this is cool. wonder how to come up with such an idea...hehe
i didnt get it all yet, but will try to figure it out completely when i have some time again.

First of all, the Nim-sum of 1, 11, and 101 is 111. Not 101.

Secondly, in order to make the explanation avaiable to all people and not only people with knowledge of the binary system:

The trick is to look at each number of dots in a row as a sum of powers of 2. For example 14 = 8 + 4 + 2, and 9 = 8 + 1. Always make the largest power of 2 into a group (so not 9=4+2+2+1 for example).

Look at all groups in all rows and count how many groups of 1 there are, how many of 2, how many of 4, 8, 16, ...

Now for my explenation I will not use the Misere game. The one that erases the last dot wins. The player that can make it so that there are an even number of groups of one size, wins. So in your example:

3 = 2 + 1
7 = 4 + 2 + 1
11 = 8 + 2 + 1

We have one group of 8, one group of 4, three groups of 2 and three groups of 1. We want to have an even number of groups of a certain size. By removing 7 dots from the third row we get:

3 = 2 + 1
7 = 4 + 2 + 1
4 = 4

Now we have two groups of 4, two groups of 2 and two groups of 1. This is what we wanted. The player whose turn it is now will lose. No matter what he does, you can always make it an even number of groups per size. Say the he erases 6 dots form the second row:

3 = 2+1
1 = 1
4 = 4

You remove 2 dots from row three:

3 = 2+1
1 = 1
2 = 2

And now it'll be clear what to do.