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.

I have no idea where to start with this question, can somebody please point me in the right direction? There's no examples of questions like this in the textbook.

  • 1
    $\begingroup$ You probably need to know what the winning strategy is first. If you don't know it, play a few games (with a friend, or left hand vs right) and see if you can work it out. Suggestion: start by experimenting with $n=5,6,7,8$. $\endgroup$ – David Dec 3 '15 at 1:25
  • $\begingroup$ Thank you for your help, I'll try doing that. $\endgroup$ – MrWiseguy818 Dec 3 '15 at 2:00

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.