Match Picking

Rules

Before the game starts, first fix the original number of matches (n) and the maximum number of matches (m) to be taken each time.

Then the two players take turn to take away 1, 2, …, m matches. The one to take the last match loses.

Play

You can choose various n and m. Try different combinations of them. Also try going first and let your opponent go first.

Think!

Is there any winning strategy? For which n, the player who starts first wins and for which n, the player who starts first loses?

Winning Strategy

To win, one should leave the last match for the other player to take. How can we ensure that we can always leave one match?

We consider the case when n = 23 and m = 4.

If you leave 6 matches for your opponent to take, then no matter how many matches he takes away, you can always leave one match for him: if he takes 1, you take 4; if he takes 2, you take 3; etc. This means that you can always make the sum of matches taken by both of you equal to 5 and thus 1 match is left.

So, how can you leave 6 matches? Using similar idea, you should leave 6 + 5 = 11 matches for your opponent. This means that we should always the number of matches leaving be a multiple of 5 plus 1. Thus when the game begins, you should take 2 matches so that 21, being 4 times 5 plus 1, matches are left. Then you can ensure that you can always win.

How if n = 21 at the beginning?

Then if you go first, you will lose if your opponent knows this strategy. So, in order to win, you should ask your opponent to go first.

Here we can generalize the winning strategy in terms of n and m.

If n is not in the form k(m + 1) + 1, then you should go first and make the number of matches remaining in that form. After that, you should take the matches such that the sum of matches taken by your opponent and you is m + 1.

If n is already in the form k(m + 1) + 1, then you should let your opponent to go first and use the method above.

If you are forced to go first, then what you can do is to hope that your opponent does not know this strategy and you make the number of matches left to be a multiple of (m + 1) plus one he goes.