Question

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, or three matchsticks. The player to remove the last matchstick wins the game.
(a) Suppose there are only 5 matchsticks left, and it is Fred’s turn. What move should Fred make to guarantee himself victory? Explain your reasoning.
(b) Suppose there are 10 matchsticks left, and it is Fred’s turn. What move should Fred 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?

Hope your writing looks readable and please draw the tree if possible.

Answer 1

Ans A)

The one who removes last stick wins and we can remove either 1,2 or 3 sticks therefore if 5 sticks are left then Fred should remove only 1 matchstick which will be left with only 4 matchsticks to choose for Barney in next round.

Barney can maximum choose 3 sticks then Fred will move final stick to win the game; If Barney removes 2 sticks then too Fred will win the game by removing 2 sticks ; If Barney removes 1 stick then too Fred will win by removing 3 sticks

hence Fred should remove only 1 stick when 5 sticks are left.

Ans B)

If 10 match sticks are left then Fred should remove 2 matchsticks so that 8 will be left

Now if Barney removes 3 matchsticks then 5 are left and we can follow part A)

If Barney removes 2 matchsticks then 6 are left and Fred can move 2 more match sticks which are left with 4 sticks to remove for Barney but Barney at most can remove 3 match sticks and hence Fred will win.

If Barney removes 1 matchstick then 7 are left and Fred can move 3 more match sticks which are left with 5 sticks to remove for Barney but Barney at most can remove 3 match sticks and hence Fred will win.

Ans C) & D)

The player who starts the game should always win if and only if he start the game by choosing 1 matchstick.

Game Plan as below

Now assume Fred starts the game and removes 1 matchstick therefore in 2nd round Barney can at most remove 3 matchsticks. The Game plan is Fred should make these sticks removal and they are 5th, 9th, 13th,17th.

In 2nd round when Barney removes any sticks between 1 to 3 then in 3rd round Fred will remove only up to 5th stick.

In 4th round Barney removes any sticks between 1 to 3 then in 4th round Fred will remove sticks up to 9th stick

similarly in the 10th round Barney is left with only 4 sticks and he can not remove more than 3 sticks and this game would be won by Fred in 11th round by removing 21st stick