Question

1. Team A and Team B are competing in the following game: There are 25 flags planted on the beach. On its turn a team may take 1, 2, 3, or 4 flags. The team that takes the last flag wins. Team A chooses first. You are the captain of Team B. Using backward induction, devise and explain a strategy that guarantees your team will win.

Answer 1

According to the question, Team A chooses first

Team A can remove 1, 2, 3, or 4 flags on a turn. So if there are 1, 2, 3, or 4 flags remaining Team A is sure to win.

1, 2, 3, 4 winning for team A

But in case of 5 flags,  If Team A removes 1 flag then leave 4 which is winning for my team B. If Team A removes 2 flags, then leave 3 and again winning for my team B. If Team A removes 3 flags then leave 2 which is also winning for my team B.

That’s the key insight: if there are 5 flags in front of team A, they will lose the game for sure. No matter what team A does, my team B can win the game.

1, 2, 3, 4 winning for team A, but loosing for my team B
5 losing for team A but winning for my team B

Now let’s examine if there are 6, 7, 8 or 9 flags. In those cases, team A can remove 1, 2, 3 or 4 flags respectively and leave 5 flags. In other words, if there are 6, 7, 8 or 9 flags, team A can move to force my team B into a losing position. This means 6, 7, 8 and 9 are winning positions for team A but loosing for my team B.

1, 2, 3, 4 winning for team A, but loosing for my team B
5 losing for team A but winning for my team B
6, 7, 8, 9 winning for team A, but loosing for my team B

Hence, the 10 flags is a losing position for team A because no matter what team A does, my team B can win the game.

1, 2, 3, 4 winning for team A, but loosing for my team B
5 losing for team A but winning for my team B
6, 7, 8, 9 winning for team A, but loosing for my team B
10 losing for team A but winning for my team B

Now, the pattern of this is becoming clear. Multiples of 5 will be losing positions for team A but winning position for my team B and non-multiples of 5 are winning positions for my team A but loosing position for my team B. Let’s expand out the calculation until we get to 25 flags.

1, 2, 3, 4 winning for team A, but loosing for my team B
5 losing for team A but winning for my team B
6, 7, 8, 9 winning for team A, but loosing for my team B
10 losing for team A but winning for my team B
11, 12, 13, 14 winning for team A, but loosing for my team B
15 losing for team A but winning for my team B
16, 17, 18, 19 winning for team A, but loosing for my team B
20 losing for team A but winning for my team B
21, 22, 23, 24 winning for team A, but loosing for my team B
25 losing for team A but winning for my team B

We can see 25 flags is a winning position for my team B. As per question team A goes first and remove 1 flag. Then team A keep removing up flags so team B is left with a multiple of 5 flags which is sure win for my team B.