Discrete Mathematics

------------------------'PROOF

METHODS

AND

INDUCTION

21

Base

case n =

1.

The

step player has no choice

but

to

remove 1 stick and lose.

For the inductive step, there are four cases:

• n =

4k

+

1:

shows that the first player loses.

We

have already handled the base case (n = 1), so

we

can assume n

~

5. Consider what the first

player might do to win:

he

can choose to remove 1, 2, or 3 sticks.

If

he removes one stick, the

remaining number

of

sticks is n - 1 = 4k. By strong induction, the player who plays at this point

should win. So the player who played

first will lose.

Similarly,

if

the first player removes two sticks, the remaining amount