Probability the Two Strongest Teams Meet in a 16-Team Knockout Final
Company: DRW
Role: Quantitative Researcher
Category: Statistics & Math
Difficulty: hard
Interview Round: Onsite
Sixteen teams with distinct skill levels are randomly assigned to the 16 starting slots of a fixed single-elimination bracket. The tournament has four rounds: the 16 teams play 8 first-round games, the 8 winners play 4 quarterfinals, the 4 remaining teams play 2 semifinals, and the 2 semifinal winners meet in the final. In every game, the stronger team wins with probability 0.9, independently of all other games.
What is the probability that the two strongest teams meet in the final?
```hint Separate placement from play
First work out which starting placements make a meeting in the final possible at all. Then consider how many games each of the two teams must win, and whom they could face along the way.
```
### Constraints and Clarifications
- Every assignment of the 16 teams to the 16 slots is equally likely.
- The bracket is fixed: later-round pairings are determined by slot positions, and there is no reseeding after a round.
- The 0.9 win probability applies to every game, regardless of how far apart the two teams' skill levels are.
- Give an exact expression and a decimal approximation.
### What a Strong Answer Covers
- The structural condition on starting slots under which two teams can meet only in the final, and the probability of that placement.
- The number of games each team must win and the strength of the opponents it can meet before the final.
- A justified independence argument when combining the placement probability with game outcomes.
- An exact final value with a sanity check, such as the limiting case in which the stronger team always wins.
### Follow-up Questions
1. What is the probability that the strongest team wins the tournament?
2. Generalize the answer to a bracket of $n = 2^k$ teams in which the stronger team wins each game with probability $p$.
3. How would the answer change if the bracket were seeded so that the two strongest teams always start in opposite halves?
Overview: Probability puzzle about a 16-team single-elimination bracket with random slot assignment, in which the stronger team wins each game with probability 0.9. Asks for the chance that the two strongest teams meet in the final, testing conditioning on bracket structure, independence of game outcomes, and careful counting.
Read the full DRW Quantitative Researcher interview experience this question came from
Community answers
Answer by 0rz...
They have to be signed in different halves... o.w., only ONE team per half can make it to the final, they can't go final together if they are in the same half.
P(diff halves) == C(2,1)*C(14,7)/C(16,8) = 8/15
each has to win ALL 3 games before final => (0.9^3)^2 == 0.9**6
=> P(meet in Final) == 8/15*0.9^6 = 0.283
P(the strongest team wins the tournament)
== 0.9^4 =0.6561
regardless of the assignment, we just need the strongest team to win ALL 4 matches.
for n=2^k teams, each wins with probability p...
P(different halves) = C(2,1)C(2^k-2, 2^(k-1)-1)/C(2^k, 2^(k-1)) = 2^(k-1)/(2^k-1)
P(wins all k-1 games before the final) = p^(2k-2)
so, P(meet in the final) == (2p^2)^(k-1)/(2^k-1)
if the strongest 2 teams always start from different halves...
then they only both need to wins ALL k-1 matches
=> P=p^(2k-2)