A while ago, my father, who is a competitive backgammon player, had a puzzle for me. He wanted to know the fraction of players remaining after a certain number of rounds of play in a triple-elimination tournament. This blog post goes over my work to figure out the answer.
A triple-elimination tournament is more-or-less how it sounds. If you lose 3 times, you’re eliminated. Since the problem doesn’t need to deal with any sort of bracket structure, I’m leaving it out completely.
In any triple-elimination tournament, there are 3 groups of players; those with zero, one, and two losses. The number of players with zero losses is easiest to figure out. After each match, there is one winner and one loser. After the first round, half of the players won, and half of the players lost. After the second round, half of the winning players won again. The proportion of players with zero losses after x rounds of play is
The number of players with one loss is a little trickier. After the first round, half of the players lost the first game. After the second round, the fraction of players with one loss is the sum of those who lost their first game and won the second, and those who won their first game and lost the second. Each of those groups comprise one quarter of the total number of players, so the fraction of players with one loss at the end of the second round is still half. After the third round, half of the half of players with one loss won their third game, and half of the quarter of players with zero losses lost their third game, so the fraction of players with one loss after round three is (1/4) + (1/8) = (3/8) After the fourth round, half of the three eighths of players with one loss won their fourth game, and one eighth of the players with zero losses lost their fourth game.
If we expand a little further, a clear pattern emerges. 1/2, 2/4, 3/8, 4/16, 5/32. The proportion of players with one loss after x rounds of play is
Finally, there are the players with two losses. Seeing as it’s not possible to lose twice in zero or one rounds of play, I’m going to start counting at x = 2 rounds.
After two rounds, one in four players lost twice. After the third round, half of those players lost for the third time, resulting in their elimination, and half won, giving one in eight players. These players are joined by the quarter of players with one loss who lost their second match, giving 3/8. After the fourth round, half of the 3/8 won, giving 3/16. These lucky few are joined by 3/16 of people with one loss who lost their fourth match, giving 6/16. After the fifth round, half of the 6/16 won, giving 6/32, who are joined by the 4/32 of people with one loss who lost their fifth match, giving 10/16. If we look at the number of rounds, and the sequence of values in the numerator, we see [(2, 1), (3, 3), (4, 6), (5, 10)], which matches the following equation:
That means the proportion of people with two losses is equal to
Now, the number of people in the tournament after x rounds (where x is greater than 2) is equal to
