$32$ teams, ranked $1$ through $32$, enter a basketball tournament that works as follows: the teams are randomly paired and in each pair, the team that loses is out of the competition. The remaining $16$ teams are randomly paired, and so on, until there is a winner. A higher-ranked team always wins against a lower-ranked team. If the probability that the team ranked $3$ (the third-best team) is one of the last four teams remaining can be written in simplest form as $\frac{m}{n}$, compute $m+n$.
(Source: PUMAC 2016 Combinatorics A)
My attempt:
The only way team $3$ doesn't get in the top $4$ is if it gets beaten by either team $1$ or $2$. We use casework and complementary counting.
Case 1: Team $3$ gets beaten by team $1$ or $2$ in the round of $32$ = $\frac{2}{31}$
Case 2: Team $3$ gets beaten by team $1$ or $2$ in the round of $16$ = $\frac{2}{15}$, but we also add the probability that $1$ and $2$ got matched up in the round of $32$. This is because there are two "subcases" in case $2$, so we add the probability of both. This is $\frac{1}{\binom{32}{2}}$ = $\frac{2}{15} + \frac{1}{496}$.
Case 3: Team $3$ gets beaten by team $1$ or $2$ in the round of $8$ = $\frac{2}{7}$, but we add the probability that $1$ and $2$ got matched up in the round of $16$. This probability is $\frac{1}{\binom{16}{2}}$ due to the same logic, but we have to multiply by $\frac{495}{496}$ because there is a $\frac{1}{496}$ chance that either $1$ or $2$ won't make it to the round of $16$. This is $\frac{2}{7}+\frac{1}{120} \cdot \frac{495}{496}$.
Adding and using complementary probability gets us an answer of $\frac{205777}{416640}$, so $m+n = 622417$.
However, the answer key makes this problem much simpler. Here's the explanation:
This is the same as putting the teams in a bracket-style tournament at random. The probability
that the teams ranked $1$ and $2$ are not in the same quarter of the draw as the team ranked $3$
is the relevant probability, and it is $\frac{24 \cdot 23}{31\cdot 30} = \frac{92}{155}, m+n = 247$.
How did they get such a simple probability? I'm also completely confused on how they got the numerator. Denominator I can understand, but I just can't figure out how they got the numerator. Is it from $4!$, and if so, how? Also, the wording is a bit unclear to me; they say "not in the same quarter of the draw as the team ranked $3$", which I'm not quite understanding. And why is my answer wrong? I used casework and complementary counting but where did I err? Thanks in advance.
Best Answer
After you assign team number $3$ a slot in the draw, there are $31$ slots remaining. Of those, $7$ are in the same quadrant of the draw as team $3$ so $24$ are not. Assign team number $1$ to one of those $31$ slots, and you'll still be "in the ball game" $\frac{24}{31}$ of the time.
Now that you've assigned two teams (team numbers $1$ and $3$), you need to assign team number $2$. There are $30$ remaining slots. Assuming you're still in the ball game, $7$ of those remaining slots are in the same quadrant as team number $3$, and the remaining $23$ are not. Thus, assuming that team numbers $1$ and $3$ are in different quadrants, the probability that teams $2$ and $3$ also are in different quadrants of the draw is $\frac{23}{30}$.
You win if both probabilities come to pass and they're independent, so your final probability is $\frac{24 \cdot 23}{31 \cdot 30}$ reduced to lowest terms.
Your calculations of cases past Case $1$ are incorrect because you can't add the probability of being beaten by either team number $1$ or $2$ to the probability that team numbers $1$ and $2$ have already played each other. You have to multiply $\frac 27$ (in Case $2$) by the probability that team numbers $1$ and $2$ have not played each other, and then add that to the product of $\frac 17$ by the probability that they have.