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...

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?