Consider a game in which there are two players, Alice and Bob. Initially there
is a pile of n coins placed on a table. The players alternate turns, with Alice playing rst.
Each player, on her or his turn, removes either one or two coins from the pile. The player
who takes the last coin wins. Use strong induction to prove that if n is congruent to 1 or 2
(mod 3) then Alice has a winning strategy (i.e. she can guarantee a win no matter what Bob
does), and if n is congruent to 0 (mod 3) then Bob has a winning strategy.

Question

Consider a game in which there are two players, Alice and Bob. Initially there
is a pile of n coins placed on a table. The players alternate turns, with Alice playing rst.
Each player, on her or his turn, removes either one or two coins from the pile. The player
who takes the last coin wins. Use strong induction to prove that if n is congruent to 1 or 2
(mod 3) then Alice has a winning strategy (i.e. she can guarantee a win no matter what Bob
does), and if n is congruent to 0 (mod 3) then Bob has a winning strategy.