Optimal strategy in a match picking game 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!
 A: 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.
A: Existence of a Strategy for Someone
I claim that for every number of matches, either the next player to move has a winning strategy (say that these numbers are "winners"), or the other player does ("losers"). We can prove this with induction (say, strong induction on the number of matches, if you're most comfortable with that).
If there is one match, then the next person to move has won the game, so 1 is a winner. If there is more than one match, then either all the moves are to winners, or not. If all the moves are to winners, then the other player will be faced with a winner no matter what, so the current number is a loser. On the other hand, if there is a move to a number that's not a winner, then by induction that move is to a loser, and the next player to move can start by handing their opponent a loser, and thereby end up winning (assuming perfect play), so the current number is a winner.
This proof shows us an important fact about losers and winners: A number is a loser when all moves are to winners (and it's not the number 1). A number is a winner when there is a move to a loser (or it's the number 1).
Winners and Losers
We can prove that the losers have the form $3*2^n-1$ and the winners are all other numbers by induction. $1$ doesn't have that form, and it's a winner.
If you're at a number of that form, you can only move to numbers greater than $3*2^{n-1}-1$ (as that would be just under half) and less than $3*2^n-1$ (since you have to remove a match), which are all winners by inductive hypothesis. As all the moves are to winners, $3*2^n-1$ must be a loser.
If you're not at a number of that form and you're not at 1, then you're somewhere between $3*2^n$ and $3*2^{n+1}-2$, inclusive (for some $n\ge0$). But then can move to a number as low as $(3*2^{n+1}-2)/2=3*2^{n}-1$ for sure. Since you can move to a loser, you're at a winner.

Terminology aside
Traditionally, in combinatorial game theory, positions/setups with a number of matches that's a winner would be called "$\mathcal N$-positions", since the next player to move has a winning strategy. The other positions are "$\mathcal P$-positions", since the previous player has a winning strategy.
Since your match game doesn't have extra rules distinguishing the two players, it's an "impartial game". And since a player who is can't move (when faced with 1 match) wins instead of loses, it's said to be following the  misère play condition.
