Induction solution for game of coins

Question

Consider a game in which, initially, there is a pile of n coins placed on a table. There are two players who alternate turns. Each player, on her or his turn, removes either one, two, or three coins from the pile. The player who takes the last coin wins. Use the strong form of induction to prove the following statement: If the number of coins currently in the pile is congruent to 1, 2, or 3 modulo 4, then the next player to play has a winning strategy, and if the number of coins currently in the pile is a multiple of 4 then the player who is not next to play has a winning strategy.

Answer 1

HINT: Show by induction on $k$ that if the statement is true for $n=4k$, then it’s also true for $n=4(k+1)$. Then show that this implies the statement for numbers $n$ that are not multiples of $4$. In each part of the proof you need to think about what a winning strategy would be for the player who has one.