HMMT-Feb 2021 comb, Problem 2

Ava and Tiffany participate in a knockout tournament consisting of a total of 32 players. In each of 5 rounds, the remaining players are paired uniformly at random. In each pair, both players are equally likely to win, and the loser is knocked out of the tournament. The probability that Ava and Tiffany play each other during the tournament is $\frac{a}{b}$, where $a$ and $b$ are relatively prime positive integers. Compute $100 a+b$.

Solution: Solution: Each match eliminates exactly one player, so exactly $32-1=31$ matches are played, each of which consists of a different pair of players. Among the $\left(\begin{array}{c}32 \\ 2\end{array}\right)=\frac{32 \cdot 31}{2}=496$ pairs of players, each pair is equally likely to play each other at some point during the tournament. Therefore, the probability that Ava and Tiffany form one of the 31 pairs of players that play each other is $\frac{31}{496}=\frac{1}{16}$, giving an answer of $100 \cdot 1+16=116$. $\fbox{116}$.

Answer: 116