Question

There are 16 equally skilled players $S_1, S_2, S_3, ......, S_{16}$ playing a knockout tournament. They are divided into 8 pairs at random. From each pair a winner is decided on the basis of a game played between the two players of the pair, and they enter into the next round. the tournament proceed in the similar way.

• A. Probability that exactly one of $S_1$ & $S_2$ is among the 4 winners of $2^{nd}$ round is
• B. The probability that $S_1$ wins the tournament given that $S_2$ enters in the semifinals is
• C. The probability that $S_1$ wins the tournament given that $S_2$ enters into final is
• D. The probability that $S_1$ is among the 4 winners of $2^{nd}$ round given that $S_2$ wins the first round is
• E. $\frac{1}{30}$
• F. $\frac{1}{20}$
• G. $\frac{1}{10}$
• H. $\frac{7}{30}$
• I. $\frac{2}{5}$

Answer 1

A-T, B-Q, C-P, D-S

Answer 2

The problem describes a knockout tournament with 16 equally skilled players. This means that in any game between two players, each player has a 1/2 probability of winning. The pairings are random at each stage.

Let's denote $P(S_i \text{ wins Rk})$ as the probability that player $S_i$ wins their game in Round k. Since players are equally skilled, $P(S_i \text{ wins Rk}) = 1/2$.

The tournament structure is:

• Round 1 (R1): 16 players -> 8 winners
• Round 2 (R2): 8 winners -> 4 winners (Quarter-finals)
• Round 3 (R3): 4 winners -> 2 winners (Semi-finals)
• Round 4 (R4): 2 winners -> 1 winner (Final)

To analyze the probabilities of players meeting, we can consider the "brackets" in the tournament.

• There are 8 pairs in R1.
• There are 4 "quarter-final brackets" (groups of 4 players who would meet in R2 if they both win R1).
• There are 2 "semi-final brackets" (groups of 8 players who would meet in R3 if they both win R1 and R2).
• There is 1 "final bracket" (group of 16 players).

The probability that two specific players, say $S_i$ and $S_j$, meet in a particular round depends on their initial placement in the bracket.

• Probability of $S_i$ and $S_j$ meeting in R1: $1/\text{ (total players - 1)} = 1/15$.
• Probability of $S_i$ and $S_j$ being in the same 4-player quarter-final bracket: $3/15 = 1/5$. If they are in the same 4-player bracket, they will meet in R1 (prob 1/3) or R2 (prob 2/3), assuming they keep winning.
• Probability of $S_i$ and $S_j$ being in the same 8-player semi-final bracket: $7/15$. If they are in the same 8-player bracket, they can meet in R1, R2, or R3.
• Probability of $S_i$ and $S_j$ being in the same 16-player final bracket: $15/15 = 1$. They can meet in R1, R2, R3, or R4.

Let's solve each part:

(A) Probability that exactly one of $S_1$ & $S_2$ is among the 4 winners of $2^{nd}$ round. Let $W_1$ be the event that $S_1$ is among the 4 winners of R2. Let $W_2$ be the event that $S_2$ is among the 4 winners of R2. For $S_1$ to be among the 4 winners of R2, $S_1$ must win its R1 game and its R2 game. $P(W_1) = P(S_1 \text{ wins R1 and R2}) = (1/2) \times (1/2) = 1/4$. Similarly, $P(W_2) = 1/4$.

We need to find $P(\text{exactly one}) = P(W_1 \cap W_2^c) + P(W_1^c \cap W_2)$. This can be calculated as $P(W_1) + P(W_2) - 2P(W_1 \cap W_2)$.

For $S_1$ and $S_2$ to both be among the 4 winners of R2 ($W_1 \cap W_2$), they must both win their first two games AND they must not meet each other in R1 or R2. This means $S_1$ and $S_2$ must be in different 4-player quarter-final brackets. The probability that $S_1$ and $S_2$ are in different 4-player quarter-final brackets is $1 - P(\text{same 4-player bracket}) = 1 - 3/15 = 12/15 = 4/5$. If they are in different 4-player brackets, their paths are independent until R3. So, P(W_1 \cap W_2) = P(\text{different 4-player brackets}) \times P(S_1 \text{ wins R1 & R2}) \times P(S_2 \text{ wins R1 & R2}) $P(W_1 \cap W_2) = (4/5) \times (1/4) \times (1/4) = (4/5) \times (1/16) = 1/20$.

Now, $P(\text{exactly one of } S_1 \text{ and } S_2 \text{ is among 4 winners of R2})$ $= P(W_1) + P(W_2) - 2P(W_1 \cap W_2)$ $= 1/4 + 1/4 - 2(1/20)$ $= 1/2 - 1/10 = 5/10 - 1/10 = 4/10 = 2/5$. So, (A) matches with (T).

(B) The probability that $S_1$ wins the tournament given that $S_2$ enters in the semifinals. Let $A$ be the event that $S_1$ wins the tournament. Let $B$ be the event that $S_2$ enters the semifinals. $S_2$ enters the semifinals means $S_2$ wins R1 and R2. $P(B) = P(S_2 \text{ wins R1 and R2}) = (1/2) \times (1/2) = 1/4$.

We need to find $P(A|B) = P(A \cap B) / P(B)$. $A \cap B$ is the event that $S_1$ wins the tournament AND $S_2$ enters the semifinals. For $S_1$ to win the tournament, $S_1$ must win all 4 games. For $S_2$ to enter the semifinals, $S_2$ must win its first 2 games. If $S_1$ wins the tournament, $S_1$ must win against $S_2$ if they meet. If $S_1$ wins against $S_2$, then $S_2$ cannot proceed further. So, for $S_2$ to enter the semifinals, they must not meet in R1 or R2.

Case 1: $S_1$ and $S_2$ are in different semi-final brackets. The probability that $S_1$ and $S_2$ are in different 8-player semi-final brackets is $1 - P(\text{same 8-player bracket}) = 1 - 7/15 = 8/15$. If they are in different semi-final brackets, they cannot meet until the final (R4). In this case, $S_1$ wins R1, R2, R3 (prob $(1/2)^3 = 1/8$), and $S_2$ wins R1, R2 (prob $(1/2)^2 = 1/4$). They meet in the final (R4), and $S_1$ wins (prob 1/2). So, $P(A \cap B \text{ and meet in R4}) = P(\text{different 8-player brackets}) \times P(S_1 \text{ wins R1,R2,R3}) \times P(S_2 \text{ wins R1,R2}) \times P(S_1 \text{ wins R4 vs } S_2)$ $= (8/15) \times (1/8) \times (1/4) \times (1/2) = 1/(15 \times 4 \times 2) = 1/120$.

Case 2: $S_1$ and $S_2$ are in the same semi-final bracket, but different quarter-final brackets. The probability that $S_1$ and $S_2$ are in the same 8-player semi-final bracket but different 4-player quarter-final brackets is $P(\text{same 8-player bracket}) - P(\text{same 4-player bracket}) = 7/15 - 3/15 = 4/15$. In this case, $S_1$ and $S_2$ will meet in the semifinals (R3) if they both win their first two games. For $S_1$ to win the tournament, $S_1$ must win R1, R2. $S_2$ must win R1, R2. They meet in R3. $S_1$ wins R3 (vs $S_2$). $S_1$ wins R4. So, $P(A \cap B \text{ and meet in R3}) = P(\text{same 8-player, not same 4-player}) \times P(S_1 \text{ wins R1,R2}) \times P(S_2 \text{ wins R1,R2}) \times P(S_1 \text{ wins R3 vs } S_2) \times P(S_1 \text{ wins R4})$ $= (4/15) \times (1/4) \times (1/4) \times (1/2) \times (1/2) = (4/15) \times (1/64) = 1/(15 \times 16) = 1/240$.

Case 3: $S_1$ and $S_2$ are in the same quarter-final bracket. This means they meet in R1 or R2. If they meet, only one can proceed. If they meet in R1 or R2, $S_2$ cannot reach semifinals and $S_1$ win tournament unless $S_1$ eliminates $S_2$. But if $S_1$ eliminates $S_2$, $S_2$ does not enter the semifinals. So, this case contributes 0 to $P(A \cap B)$.

So, $P(A \cap B) = 1/120 + 1/240 = 2/240 + 1/240 = 3/240 = 1/80$. $P(A|B) = P(A \cap B) / P(B) = (1/80) / (1/4) = 4/80 = 1/20$. So, (B) matches with (Q).

(C) The probability that $S_1$ wins the tournament given that $S_2$ enters into final. Let $A$ be the event that $S_1$ wins the tournament. Let $C$ be the event that $S_2$ enters the final. $S_2$ enters the final means $S_2$ wins R1, R2, and R3. $P(C) = P(S_2 \text{ wins R1, R2, R3}) = (1/2) \times (1/2) \times (1/2) = 1/8$.

We need to find $P(A|C) = P(A \cap C) / P(C)$. $A \cap C$ is the event that $S_1$ wins the tournament AND $S_2$ enters the final. For $S_1$ to win the tournament, $S_1$ must win all 4 games. For $S_2$ to enter the final, $S_2$ must win its first 3 games. If $S_1$ wins the tournament and $S_2$ enters the final, they must meet in the final (R4), and $S_1$ must win that game. This implies they must not meet in R1, R2, or R3. This means they must be in different semi-final brackets. The probability that $S_1$ and $S_2$ are in different 8-player semi-final brackets is $1 - 7/15 = 8/15$. If they are in different semi-final brackets, they can only meet in the final (R4). So, $P(A \cap C) = P(\text{different 8-player brackets}) \times P(S_1 \text{ wins R1,R2,R3}) \times P(S_2 \text{ wins R1,R2,R3}) \times P(S_1 \text{ wins R4 vs } S_2)$ $= (8/15) \times (1/8) \times (1/8) \times (1/2) = 1/(15 \times 8 \times 2) = 1/240$.

$P(A|C) = P(A \cap C) / P(C) = (1/240) / (1/8) = 8/240 = 1/30$. So, (C) matches with (P).

(D) The probability that $S_1$ is among the 4 winners of $2^{nd}$ round given that $S_2$ wins the first round. Let $W_1$ be the event that $S_1$ is among the 4 winners of R2. Let $F_2$ be the event that $S_2$ wins the first round. $P(F_2) = 1/2$.

We need to find $P(W_1|F_2) = P(W_1 \cap F_2) / P(F_2)$. $W_1 \cap F_2$ is the event that $S_1$ wins R1 & R2, AND $S_2$ wins R1.

Case 1: $S_1$ and $S_2$ meet in R1. The probability that $S_1$ and $S_2$ meet in R1 is $1/15$. If they meet in R1, $S_1$ must win R1 (prob 1/2) and $S_2$ must lose R1 (prob 1/2). In this case, $S_2$ does not win R1. So, this case contributes 0 to $P(W_1 \cap F_2)$.

Case 2: $S_1$ and $S_2$ do not meet in R1. The probability that $S_1$ and $S_2$ do not meet in R1 is $1 - 1/15 = 14/15$. If they don't meet in R1, their R1 outcomes are independent. $S_1$ wins R1 (prob 1/2). $S_2$ wins R1 (prob 1/2). Now, $S_1$ and $S_2$ are among the 8 winners of R1. For $S_1$ to be among the 4 winners of R2, $S_1$ must win its R2 game. For $S_2$ to win R1, $S_2$ has already won R1. If $S_1$ and $S_2$ did not meet in R1, they are 2 of the 8 players in R2. They might meet in R2. The probability that $S_1$ and $S_2$ meet in R2, given they both won R1 and didn't meet in R1: There are 7 other players for $S_1$ to be paired with in R2. So, $1/7$. If they meet in R2, $S_1$ must win R2 (prob 1/2). If $S_1$ wins, $S_2$ loses, so $S_2$ does not proceed to R3, but $S_2$ did win R1. So, $P(W_1 \cap F_2 \text{ and meet in R2}) = P(\text{not meet R1}) \times P(S_1 \text{ wins R1}) \times P(S_2 \text{ wins R1}) \times P(\text{meet R2 | won R1, not meet R1}) \times P(S_1 \text{ wins R2 vs } S_2)$ $= (14/15) \times (1/2) \times (1/2) \times (1/7) \times (1/2)$ $= (14/15) \times (1/4) \times (1/7) \times (1/2) = (14 \times 1) / (15 \times 4 \times 7 \times 2) = (2 \times 7) / (15 \times 56) = 1 / (15 \times 4) = 1/60$.

The probability that $S_1$ and $S_2$ do not meet in R2, given they both won R1 and didn't meet in R1 is $1 - 1/7 = 6/7$. If they don't meet in R2, their R2 outcomes are independent. $S_1$ wins R2 (prob 1/2). So, $P(W_1 \cap F_2 \text{ and not meet in R2}) = P(\text{not meet R1}) \times P(S_1 \text{ wins R1}) \times P(S_2 \text{ wins R1}) \times P(\text{not meet R2 | won R1, not meet R1}) \times P(S_1 \text{ wins R2})$ $= (14/15) \times (1/2) \times (1/2) \times (6/7) \times (1/2)$ $= (14/15) \times (1/4) \times (6/7) \times (1/2) = (14 \times 6) / (15 \times 4 \times 7 \times 2) = (2 \times 7 \times 6) / (15 \times 56) = (12 \times 7) / (15 \times 56) = (3 \times 4 \times 7) / (15 \times 56) = (3 \times 7) / (15 \times 14) = 1 / (5 \times 2) = 1/10$.

So, $P(W_1 \cap F_2) = 1/60 + 1/10 = 1/60 + 6/60 = 7/60$. $P(W_1|F_2) = P(W_1 \cap F_2) / P(F_2) = (7/60) / (1/2) = 7/60 \times 2 = 7/30$. So, (D) matches with (S).

Summary of matches: (A) - (T) (B) - (Q) (C) - (P) (D) - (S)