0
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Done, now what? $\endgroup$ Mar 27, 2015 at 7:41

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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