Two players begin to play with 1000 coins. Every player in his turn can replace the current amount of coins $\mathcal N $ in $\mathcal N-1$ or in $\lfloor \mathcal N/2 \rfloor $.
The first player that reaches 0 wins. Who of them has a winning strategy?
Now I've been given a HINT which I don't understand.
HINT: Solve the game first for odd $\mathcal N$ with strategy stealing.
Could use some help to get me going.
For the hint:
If $N$ is odd. Then the action $N\rightarrow N-1$ and then $N-1\rightarrow \lfloor \frac{N-1}{2}\rfloor$ leads to the same result as the action $N\rightarrow \lfloor\frac{N}{2}\rfloor$. Therefore the first player can "steal" the winning strategy.
We prove by induction on $N$ that for odd values of $N$ player $1$ has a winning strategy:
For $N=1$ - trivial. Assuming for $N$ we prove for $N+2$.
Consider the move $N+2\rightarrow N+1$ of player $1$. We now study the game from the starting point $N+1$.
If player $1$ (who's not the first anymore) has a winning strategy then we're done. Otherwise player $2$ has winning strategy, but by induction hypothesis the winning strategy cannot begin with $N+1\rightarrow N$. We conclude that the winning strategy of player $2$ begins with the move $N+1\rightarrow \lfloor \frac{N+1}{2}\rfloor$.
In that case we're back to the original case (with $N+2$ coins) and player $1$ will play $N+2\rightarrow \lfloor\frac{N+2}{2}\rfloor.$ Since $\lfloor\frac{N+2}{2}\rfloor = \lfloor \frac{N+1}{2}\rfloor$ we have that player $1$ has a winning strategy. This completes the induction.
Now for the question: If we begin with $1000$ player $1$ has two options moving to $500$ or moving to $999.$ If he moves to $999$ he will lose (because player $2$ begins). If he moves to $500$ player $2$ has two options moving to $250$ or moving to $499$ again if player $2$ moves to $499$ he loses. Now player $1$ can either move to $249$ and lose or move to $125$ and lose.
We conclude that player $2$ has a winning strategy which can be described as follows:
If player $1$ removes $1$, then there are $999$ left and we prove player $2$ has a winning strategy.
Otherwise if player $1$ removes $500$, then player $2$ removes another $250$.
Now every action of player $1$ will lead to an odd number of coins, hence player $2$ has a winning strategy.