# Consider a game in which two players, Fred and Barney, take turns removing matchsticks from a pile..

Consider a game in which two players, Fred and Barney,

take turns removing matchsticks from a pile. They start with 21 matchsticks,

and Fred goes first. On each turn, each player may remove either one, two,

three, or four matchsticks. The player to remove the last matchstick wins the

game.

(a) Suppose there are only six matchsticks left, and it

is Barney’s turn. What move should Barney make to guarantee himself victory?

Explain your reasoning.

(b) Suppose there are 12 matchsticks left, and it is

Barney’s turn. What move should Barney make to guarantee himself victory?

(Hint: Use your answer to part (a) and roll back.)

(c) Now start from the beginning of the game. If both

players play optimally, who will win?

(d) What are the optimal strategies (complete plans of

action) for each player?