0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You write "Here is the question" but I don't see a question mark anywhere. What is your question? $\endgroup$ – bof Dec 16 '17 at 23:23
  • $\begingroup$ 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. $\endgroup$ – Miranda Ashfield Dec 17 '17 at 0:16
  • $\begingroup$ 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? $\endgroup$ – bof Dec 17 '17 at 0:22
  • $\begingroup$ 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. $\endgroup$ – Miranda Ashfield Dec 17 '17 at 0:32
  • $\begingroup$ 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.$ $\endgroup$ – bof Dec 17 '17 at 0:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.