Game with matches. Very interesting mathematical problem.

Question

Suppose you have a set of matches. You arrange them in 9 rows such that the first row has one match the second two matches the third three and so on until the ninth row which has nine matches. There are two players A and B. They play in turns and on each round a player can pick a row and remove as many matches as he wants from that specific row from the game. The winner is the player to remove the last match (if there are two say remaining matches on a single row you are free to remove them both and win). Is there a way for any of the two players to guarantee a win? if so what strategy should they follow? Say player A plays first.

Answer 1

This game is Nim. If you read the Wikipedia article about it, you will see how to win by decomposing the rows into their binary sums:

1 = 1
2 =     2  
3 = 1 + 2
4 =         4
5 = 1     + 4
6 =     2 + 4
7 = 1 + 2 + 4
8 =             8
9 = 1         + 8

Cancelling the numbers by pairs down the columns, there is an extra $1$ left over. (In other words, there is an even number of $2$s, $4$s, and $8$s, but an odd number of $1$s.) In a winning position, all the numbers will cancel out in pairs. Therefore, a winning move would be to remove $1$ stick from the row of $9$, for instance.