Consider the following game:
Two players alternately take one or two stones from a pile of stones. The objective of each player is to take, in total, an even number of stones. Suppose that in the beginning the pile has an odd number of stones $n$, so that one of the players wins and another loses.
I would like to know, what player has the winning strategy here.
If $n = 1$ the second player is the one, who wins, as the first player takes the only stone and loses immediately.
If $n = 3$ the first player wins by taking two stones and reducing the game $n = 1$ on second player's turn.
However, I have no idea how to get the solution for an arbitrary odd $n$.
This question (not all of it, however, but only the quoted "rules of the game") was initially posted by @kris, but got deleted as a PSQ. However, this question seemed too interesting to ignore so I reposted it (with added context).
Best Answer
Label a state (where it is your turn) by $(n,m)$ where $n$ is the number of stones in the pile and $m$ is the parity ($0= even$, $1=odd$) of the number of stones you have. Note that the total number of stones is odd, so if $n$ is even your opponent's number of stones has the opposite parity to yours, while if $n$ is odd your opponent's number has the same parity as yours. Thus $(0,0)$, $(1,1)$ are winning positions and $(0,1)$ and $(1,0)$ are losing.
By induction, I find the following:
$(4k,0)$ is a win, $(4k,1)$ is a loss
$(4k+1,0)$ is a loss, $(4k+1,1)$ is a win
$(4k+2,0)$ is a win, $(4k+2,1)$ is a win.
$(4k+3,0)$ is a win, $(4k+3,1)$ is a loss.
Thus from $(4k,0)$ (if $k>0$) you take one stone, leaving your opponent in the losing position $(4k-1,1)$. From $(4k,1)$ you have a loss, as you must leave your opponent with either $(4k-1,0)$ or $(4k-2,1)$, both wins. Similarly in other cases.