Name: Mark

Who is asking: Teacher
Level: Secondary

Question:
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?

You need to look at a pattern starting with the positions with the fewest matches. We will write (x,y) to represent the position with x matches on the left pile and y matches on the right pile.

The two positions with only one match, (1,0) and (0,1), are losing positions: A player facing such a position must remove the last match and lose.

Next, a player is in a winning position if there is a way to remove matches so that what remains is one of the losing positions characterised above. (2,1), (2,0), (1,2), (1,1) and (0,2) are all winning positions.

Next, a player is in a losing position if all possible ways to remove matches will result in one of the winning positions characterized above. (3,0), (2,2) and (0,3) are losing positions.

This gives us more winning positions: (4,1), (4,0), (3,3), (3,2), (3,1), (2,3), (1,4), (1,3), (0,4)

And then more losing positions: (5,0), (4,2), (2,4), (0,5)

And then more winning positions: (6,1), (6,0), (5,3), (5,2), (5,1), (4,3), (3,5), (3,4), (2,5), (1,6), (1,5), (0,6).

And then more losing positions: (7,0), (6,2), (4,4), (2,6), (0,7).

And so on. These lists become longer and longer, so at some point you need to look for a simple pattern that characterises the losing positions and the winning positions. Then you will need to test whether your characterisation is correct. The first step is to experiment by playing it out, and see if you always win when starting from one of your "winning positions". In this way, if you get convinced that your characterisation is correct, then you can try to prove that from any of your "winning positions", there is always a play that reduces the piles to a "losing position", while any play from a "losing position" brings the piles back to a "winning position".

Let me know if you find the pattern.