0
$\begingroup$

Consider the following two player game. A pile of coins is places on a table. There are two players, Alice and Bob, who alternate turns removing one, two or three coins from the pile. Alice goes first. The player who takes the last coin wins. Use induction to prove that Alice has a winning strategy (i.e. she can play so as to guarantee a win) if the number of coins in the pile is not a multiple of 4, and Bob has a winning strategy if the number of coins in the pile is a multiple of 4.

Interesting question. I can prove it in my brain but i'm not quite sure how to prove it using induction. thanks

$\endgroup$
3
  • $\begingroup$ If you want an intuition for the winning strategy, try playing the game with yourself with a small number of coins. $\endgroup$ Commented Oct 19, 2017 at 8:05
  • $\begingroup$ To what field is this question related? Is it really logic? Or maybe probability theory or analysis? Define first what "has a winning strategy" means and try to put this claim in mathematical terms, then think about what the induction(s) start with. $\endgroup$
    – RoyPJ
    Commented Oct 19, 2017 at 8:08
  • $\begingroup$ en.wikipedia.org/wiki/Nim $\endgroup$
    – DanielV
    Commented Oct 19, 2017 at 9:00

1 Answer 1

2
$\begingroup$

The standard strategy for solving problems like this starts with thinking that you're in the middle of playing this game with $0$ coins in the pile and your turn, and see who wins (it has to be your opponent, because on their previous turn, they removed the last coin and won).

The problem already tells you that modulo 4 is important, so next we look at what happens if there instead are $1, 2, 3$ or $4$ coins and your turn. Can the you win any of them? Can your opponent guarantee a win in any of them?

Next, for $5, 6, 7$ or $8$, can you force the opponent into a position that the previous paragraph deemed as "the current player loses"? If not, can your opponent do that to you no matter what you try?

A pattern should start to emerge. What does the winning strategy seem to be? With the intuition you've built from working through the above, it shouldn't be too hard to prove by doing the above paragraph of $5, 6, 7, 8$ in general using induction. (The induction parameter isn't really "How many coins there are on the table", but rather "How many groups of four coins there are", and then the induction step itself is split into four cases depending on how many coins are left modulo 4.)

$\endgroup$
1
  • $\begingroup$ very helpful thanks $\endgroup$
    – UnXnown
    Commented Oct 19, 2017 at 8:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .