2 students play the Nim game as follows: There is only 1 heap of stones, they can take from the heap $2^x$ ($x$ can be 0) number of stones each time. The student who has taken the last stone wins. For which number of stones does the first play win? How should he play? Prove that strategy works.
My approach: I have made a guess that the first player is the winner if number of stones is not a multiply of 3. So for the case when the number of stones is 3, the second player just takes all the remaining stones. I wonder if induction would be a valid approach ?
Let's prove that first player will win if number of stones is not a multiply of 3.
First, for $N = 3$, player 1 will lose since player 2 will take all the remain stones. If $N = 3k$, for $k = 1$ we proved that player 1 will lose. Suppose it is true for $k \ge 1$, we need to prove it holds for $k + 1$.
$N = 3(k+1) = 3N + 3 $.
Clearly, player 1 will lose.
If $N = 3k + 1$, for $3k$ player 2 will win then for then for $3k + 1$, player 1 will win by taking the final stone.
Similarly if $N = 3k + 2$, player 1 will take 2 remaining stones.
Therefore the first player will win if the number of stones is not multiply of 3.