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 the strong form of 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 the strong form of 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.

anonymous · Answer

I mean i get why they'd have a winning strategy, but how do i prove this ...

nnesha · Answer

$\color{Red}{Welcome}$ $\color{blue}{To}$ $\color{Pink}{Open :) Study}$

shadowlegendx · Answer

Alice and Bob kissed each other and lived happily ever after c;