Welcome to NRICH.

 
Taking matches
By Rachelle Najman (T4009) on Wednesday, May 2, 2001 - 01:46 am:

The following problem is taken from Mason's text called Thinking Mathematically. I am finding it rather difficult and would be greatly appreciative if you can provide me with some assistance in explanation.

"Taking Matches" (p.196)
Two piles of matches are on a table. A player can remove a match from either pile or a match from both piles. The player who takes the last match loses. If there are two players, how should you play?

Any detailed explanation would be of great use and help, so thank you!

By Kerwin Hui (Kwkh2) on Thursday, May 3, 2001 - 02:21 pm:

Notice that (1,n), (0,2n) are winning configuration, and (2,2) is a losing configuration. You will have to aim to leave the other player with (2,2) configuration.

Now suppose you leave your opponent with (m, n) configuration, m and n are even number >2. Now no matter how your opponent play, you can leave him/her with (m', n') configuration again, m' n' being even and at most 2.

Now we see that the configuation (2, even>2) is the critical configuration. If your opponent takes anything from the pile of 2, he/she will lose. Hence we will be left with the (2,odd>1) configuration, and we can take one from the odd pile to make again, (2, even) configuration.

So we conclude that (non-zero even, non-zero even) is a losing configuration if neither pile is empty. We can always leave the opponent with this configuration unless we started off taking matches from (even, even) configuration, or (empty, odd).

So our strategy for the first move is to leave the opponent with either (0,2n-1) configuration or (2m, 2n) configuration.

Kerwin