Team Ordering
An intriguing puzzle asked in SIG junior quant interview
Suppose you have the results of a completed round-robin chess tournament in which n teams played each other once. Assuming there were no ties, is it always possible to list the teams in a sequence so that every team won the game with the team listed immediately after it?
Try to solve this problem yourself before moving on to the solution below
.
.
.
.
.
.
Solution
The short answer is yes
Here is an algorithm you can use to prove it:
The following recursive algorithm solves the puzzle. If n = 1, the problem is solved. If n > 1, solve the problem recursively for an arbitrarily chosen group of n − 1 teams. Then scan the obtained list of these n − 1 teams to insert the team not included in the group right before the first team on the list that lost to it in the tournament. If there is no such team—that is, if the team not yet on the list lost all its games to the teams on the list—insert that team at the end of the list.
.
.
😃 Over to you: Were you able to solve this?
👉 If you liked this post, don’t forget to leave a like ❤️. It helps more people discover this newsletter on Substack and tells us that you appreciate solving these weekly questions. The button is located towards the bottom of this email.
👉 If you love reading this newsletter, feel free to share it with friends!