4

$2^{n}$ players enter a single elimination tennis tournament. You can assume that the players are of equal ability.

enter image description here

Find the probability that two particular players meet each other in the tournament.

I could't make a serious attempt on the question, hope you can excuse me this time.

please delete me
  • 1,201

3 Answers3

2

Assume that the initial placement of players is random. Otherwise, your answer would depend on where these 2 players are placed.

There are $2^n-1$ games involving a pair of players that occur. There are ${2^n \choose 2}$ pairs of players.

Hence, the probability that 2 players meet is $\frac{ 2^n-1} { 2^n \choose 2} = \frac{1}{2^{n-1} }$.

Calvin Lin
  • 68,864
  • Nice answer! Saves a lot of time in exams :) – please delete me Jul 01 '13 at 17:25
  • Why are each of the $2^n-1$ games involving the pair of players equally likely? – Isaac Greene Mar 12 '18 at 02:59
  • @IsaacGreene Because the initial placement of players is equally likely. So, the probability that players A-B will play a game in the 1st/2nd/3rd/4th/5th round is the same as the probability that players X-Y will play a game in the 1st/2nd/3rd/4th/5th round. Hene the sum of probabilities is the same. – Calvin Lin Jun 09 '18 at 02:10
2

We will make the usual unreasonable assumptions. We also assume (and this is the way tournaments are usually arranged) that the initial locations of the players on the left of your picture are chosen in advance. We also assume (not so reasonable) that the locations are all equally likely.

Work with $n=32$, like in your picture. It is enough to show the pattern. Call the two players A and B. Without loss of generality, we may, by symmetry, assume that A is the player at the top left of your picture.

Maybe they meet in the first round. Then player B has to be the second player in your list. The probability of this is $\frac{1}{31}$.

Maybe they meet in the second round. For that, B has to be $3$ or $4$ on your list, and they must both win. The probability is $\frac{2}{31}\frac{1}{2^2}$.

Maybe they meet in the third round. For that, B must be one of players $5$ to $8$, and each player must win twice. The probability is $\frac{4}{31}\frac{1}{2^4}$.

Maybe they meet in the fourth round, probability $\frac{8}{31}\frac{1}{2^6}$.

Or maybe they meet in the final, probability $\frac{16}{31}\frac{1}{2^8}$.

Add up. For the sake of the generalization, note we have a finite geometric series.

André Nicolas
  • 507,029
  • I understand how you got $\frac{1}{32}$ for the probability of them meeting in the first round but how did you get $\frac{2}{31}$ for the second one (I understand were the $\frac{1}{4}$ comes from). Thank you! – please delete me Jul 01 '13 at 05:13
  • Remember WLOG A is top left player. The probability they meet in the first round is $\frac{1}{31}$, not $\frac{1}{32}$. To meet A in the second round (look at your picture, very helpful) player B has to be in positions $3$ or $4$. If lower they have to wait to meet. So there are $2$ positions for B (and they both have to win their first round games, but you see that). – André Nicolas Jul 01 '13 at 05:22
  • Makes a lot of sense now! Thank you! – please delete me Jul 01 '13 at 05:32
  • 1
    You are welcome. Much less insightful, however, than Calvin Lin's answer! Indeed rather plodding. But works. – André Nicolas Jul 01 '13 at 06:00
2

First off, an even number of players is a necessary but not sufficient condition for a full balanced tournament. Fir this you need $P=2^R$ where $R$ is the number of rounds (including finals, semis etc). I will assume this is what you are after.

Without loss of generality, let Player 1 occupy the first slot in the draw.

For the players to meet in the first round Player 2 must be in Slot 2, for round 2 - slot 3 or 4, round 3 - slot 5 to 8, etc. In general, for the players to meet in round $r\in 1,\dots,R$, there are $2^{r-1}$ slots available. Given that Player 2 is randomly allocated to one of $2^R-1$ slots, the probability of a potential meeting in round $r$ is

$$S(r)=\frac{2^{r-1}}{2^R-1}$$

The probability that each player makes round $r$ is $\left(\frac{1}{2}\right)^{r-1}$.

The probability that both do is therefore $\left(\frac{1}{2}\right)^{2(r-1)}$

So, the probability that they meet in round $r$ is $$\begin{align} M(r)&=\left(\frac{1}{2}\right)^{2(r-1)}\frac{2^{r-1}}{(2^R-1)}\\ &=\left(\frac{1}{2}\right)^{(r-1)}\frac{1}{(2^R-1)} \end{align}$$

And that they meet in any round is

$$\begin{align} M&=\sum_{r=1}^R \left(\frac{1}{2}\right)^{r-1} \frac{1}{(2^R-1)}\\ &=\sum_{r=0}^{R-1} \left(\frac{1}{2}\right)^{r} \frac{1}{(2^R-1)}\\ &=\frac{1-\left(\frac{1}{2}\right)^R}{1-\frac{1}{2}}\frac{1}{(2^R-1)}\\ &=2\frac{2^R-1}{2^R}\frac{1}{(2^R-1)}\\ &=2^{1-R}\\ \end{align}$$

Sanity check!

For 2 players $R=1, p=1$; 4 players $R=2, p=\frac{1}{2}=\frac{1}{3}\text{Rd1}+\frac{1}{6}\text{Rd2}$; 8 players $R=2, p=\frac{1}{4}=\frac{1}{7}\text{Rd1}+\frac{1}{14}\text{Rd2}+\frac{1}{28}\text{Rd3}$ - Sanity check passed.

Dale M
  • 2,813