# Strong induction: Game of Nim

I have a question regarding using strong induction to prove a concept relevant to the Game of Nim.

Here is the question: The game of Nim is a two player game where each player takes turns removing either 1,2 or 3 coins from a pile of coins. The player who removes the last coin loses. Whenever the number of coins is $m \in \mathbb{N}$ such that $m \equiv 1 \ (mod \ 4)$ (That is, $m=4n + 1$ for a non negative integer $n$) the second player has a winning strategy no matter what the first player does. Use strong induction on $n$ to prove this.

So far I've got that if the number of coins is not a multiple of $4$ the second player has a winning strategy and that the number of groups is $4$ is what we are investigating in the induction, not the number of coins.

Thanks in advance.

• You write "Here is the question" but I don't see a question mark anywhere. What is your question? – bof Dec 16 '17 at 23:23
• Sorry that was supposed to a +, typo! And I am wondering how to prove the statement about the second player having a winning strategy no matter what using strong induction. – Miranda Ashfield Dec 17 '17 at 0:16
• You wrote "if the number of coins is not a multiple of $4$ the second player has a winning strategy." How does the second player win if the number of coins is $2$ and the first player takes one coin? – bof Dec 17 '17 at 0:22
• I was just going off what was given in the question, it says that when the number of coins (m) is m=4n+1 than the second player has a winning strategy. So I am assuming the base case here is when n=1, the number of coins is 5 and the second player wins no matter what the first player picks. After the base case I'm not sure how to proceed. – Miranda Ashfield Dec 17 '17 at 0:32
• I'm not sure if you're saying you do know or you don't know how the second player can win when the number of coins is $5.$ – bof Dec 17 '17 at 0:36