Players and tournaments

Question

16 players take part in a tennis tournament. The order of the matches is chosen at random. If there is a player better than the other one then the better one wins find the :

a)probability that all the four best place reach the semifinals

b)probability that sixth best reaches the semifinals

My attempt:

I did realise that we need to select 8 players out of 12 less better players so (12C8*8C2*6C2*4C2*2*2*2) in the numerator /16C2*8C2 in the denominator. But I can't understand why this comes out to be >1. This means I am doing a mistake

Please help me out.

Answer 1

I am assuming the way the tournament works is that there is a first round with $8$ games, then the $8$ winners of the first round play a second round of $4$ games, then the winners of the second round enter the semi-final. In order for the top $4$ players to all play in the semi-final, no two of them can play against each other in either of the first two rounds.

For the sake of exposition, let's say the top four are the players numbered $1,2,3$ and $4$. So what is the probability that player $1$ does not play another of the top four in his first game? There are $15$ other players, of which $3$ are also in the top $4$. So the probability that player $1$ does not play another of the top $4$ is $12/15$.

Assuming player $1$ does not play another player in the top $4$, what is the probability that player $2$ does not play another in the top $4$? Excluding player $1$ and his opponent, there are $13$ players left, of which player $2$ must avoid $2$. So the probability that player $2$ does not play another in the top $4$, given that player $1$ doesn't, is $11/13$.

Proceeding in this way, we see that the probability that all top $4$ players make it through the first round is $$\frac{12}{15} \cdot \frac{11}{13} \cdot \frac{10}{11} \cdot \frac{9}{9}$$ and the probability that all top $4$ players make it through the second round, given that they made it through the first round, is $$\frac{4}{7} \cdot \frac{3}{5} \cdot \frac{2}{3} \cdot \frac{1}{1}$$ So the probability that the top $4$ all make it to the semi-final is $$\frac{12}{15} \cdot \frac{11}{13} \cdot \frac{10}{11} \cdot \frac{9}{9} \cdot \frac{4}{7} \cdot \frac{3}{5} \cdot \frac{2}{3} \cdot \frac{1}{1}$$

* EDIT *

The second part of the problem asks for the probability that player $6$ survives to the semi-finals. Let's say his portion of the tournament bracket looks like this:

6   A   B   C
|   |   |   |
+-6-+   +-?-+
  |       |
  +---6---+

Player $6$ survives to the semi-final exactly when all the other three players in his bracket of four are not in the top $6$, i.e, are in the set $\{7, 8, 9, \dots ,16\}$. There are $\binom{15}{3}$ ways to select the other three players in the bracket. Of these, $\binom{10}{3}$ consist entirely of players not in the top $6$. So the probability that player $6$ survives to the semi-final is $$\frac{\binom{10}{3}}{\binom{15}{3}} = \frac{10 \cdot 9 \cdot 8}{15 \cdot 14 \cdot 13}$$

Answer 2

The possible ways to organise the matches of the tournament is in bijection with permutations on $\{1, \dots, 16 \}$. Here we denote $1$ as the best player and $16$ as the worst player. Given a permutation $\sigma$, the rounds are as follows. In round one player $\sigma(2i-1)$ plays $\sigma(2i)$ for each $i \in \{1, \dots, 8 \}$ and then winner is $W_1(i) = \min(\sigma(2i-1), \sigma(2i))$. Then in round two, player $W_1(2i-1)$ plays $W(2i)$ for each $i \in \{1,2,3,4 \}$ and the winner is denoted $W_2(i)$ and so on for the remaining rounds.

In order for the four best players to reach the semi-finals, it is equivalent to saying that the four best players never play against each other before the semi-finals. These are permutations for which $\sigma^{-1}(i_1) \in \{1, \dots, 4 \}, \sigma^{-1}(i_2) \in \{5, \dots, 8 \}, \sigma^{-1}(i_3) \in \{9, \dots, 12 \}, \sigma^{-1}(i_4) \in \{1, \dots, 16 \}$ where $\{i_1, i_2, i_3, i_4\} = \{1,2,3,4 \}$.

To count such permutations, let's begin by assuming $i_1 = 1, i_2 = 2, i_3 = 3, i_4 = 4$. There are four possible options for $\sigma^{-1}(1)$, similarly for the others. Then there are $(n-4)!$ choices for the remaining entries of $\sigma^{-1}$. We could have permuted $i_1, \dots, i_4$ in one of $4!$ ways so the total number of permutations is $4^4 (n-4)! 4!$.

For the second part, you can figure our the considions you need for your permutation to satisfy in order for the sixth best player to reach the semi finals. Hint: it is the same as saying that player six never plays against players one to five in the first or second round.