Problem of the Week
Problem D and Solution
Game Theory

Problem

Five video game players are preparing for a team tournament. Each player has mastered a unique secret strategy for the game. To win the finals, every player needs to know all five strategies.

Because of the tournament’s practice facility rules, players can only practice in 1v1 private matches. So during a team practice round, two separate 1v1 matches happen simultaneously (involving four players total with two players in each 1v1), while the fifth player sits out. When two players play a 1v1 match, they teach each other all the strategies they currently know, including ones they learned from opponents in previous practice rounds.

What is the minimum number of practice rounds required for all five players to learn all five secret strategies?

This problem was inspired by a past Beaver Computing Challenge (BCC) problem.

Solution

In this solution, we will first show that in order for each player to learn all five secret strategies, at least four practice rounds are needed. Then we will show that this is possible in exactly four rounds. Thus, we will conclude that the minimum number of rounds needed is four.

We start by naming the video game players Gamers A, B, C, D, and E. In the first practice round, two 1v1 matches can take place, and one gamer will sit out. Suppose Gamer E sits out the first round. Since Gamer E was not involved, Gamer E’s secret strategy is known only by Gamer E. Therefore, it is not possible for anyone to know all five secret strategies after one round.

In the second round, Gamer E could play a 1v1 match or Gamer E could sit out again.

• Suppose Gamer E plays a 1v1 match. Then only two players would know Gamer E’s secret strategy. In the third round, these two players could play against at most two other players, so after three rounds, at most four players would know Gamer E’s secret strategy. Therefore, at least one more round would be needed, and so at least four rounds in total are needed.

• Suppose Gamer E sits out again on the second round. Then in the third round Gamer E could play a 1v1 match and so only two players would know Gamer E’s secret strategy. Using similar reasoning to that above, we can show that in this case, at least five rounds in total would be needed.

We have shown that at least four practice rounds are needed if Gamer E plays a 1v1 match in the second round. We will now show that this can be done in exactly four rounds.

In the first round, suppose Gamer A plays against Gamer B, Gamer C plays against with Gamer D, and Gamer E sits out.

We can summarize the secret strategies each gamer knows after the first round in the following table.

In the second round, suppose Gamer E plays against Gamer A, Gamer B plays against Gamer C, and Gamer D sits out. We can summarize the secret strategies each gamer knows after the second round in the following table.

In the third round, suppose Gamer A plays against Gamer C, Gamer D plays against Gamer E, and Gamer B sits out. Then the following table summarizes the secret strategies each gamer knows after the third round.

In the fourth round, Gamer B can play against any other player to learn Gamer E’s secret strategy. No other 1v1 match needs to take place in this round, as the remaining players all know all five secret strategies.

We have shown that at least four practice rounds are needed and we’ve also shown that it is possible for each player to learn all the secret strategies in exactly four rounds. Therefore, the minimum number of practice rounds required for each player to learn all five secret strategies is four.

Extension:
Suppose there were six players instead of five, each with their own secret strategy. Determine the minimum number of practice rounds required for all six players to learn all six secret strategies. You may be surprised by the result.