[Math] Optimal strategy in a match picking game

combinatorial-game-theory

I faced this exercise making a practice exam and couldn't find the answer:


Question:

2 players play the following game with matches. Each player can take in turn some matches from a bunch of matches, at least one and at most half of the remaining matches. The player who is confronted with the last match wins. Find the optimal strategy for playing this game.


I hope someone can help me finding the answer!

Best Answer

A hint:

Write the numbers from $1$ to $25$ or so in a row and below each number $k\geq1$ recursively write a $W$ if you are sure that $k$ matches left is a winning position, and an $L$ if you are sure that $k$ matches left is a losing position: $$\matrix{1&2&3&4&5&\ldots&25 \cr W&L&\ldots\cr}$$ A position is winning if you can put the opponent into a loosing position by taking an appropriate number of matches, and is losing if all allowed moves lead to a winning position for the opponent.

When you don't see the pattern by then replace $25$ by $60$ or so.