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.

  • $\begingroup$ I dont guess you can make a plan to guarantee a win, since it depends on each player move during the game and mentality and how the opponent thinks and plays. $\endgroup$ – Mohamad Misto May 10 '15 at 14:31
  • $\begingroup$ You would have to prove that $\endgroup$ – vounoo May 10 '15 at 14:34
  • 2
    $\begingroup$ The game is called Nim, there is always a winning strategy for the first or second player, which is described here: en.wikipedia.org/wiki/Nim $\endgroup$ – Peter Webb May 10 '15 at 15:01

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.