Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$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.

share|improve this question
    
Is the number of players a power of $2$? Is a game decided on the flip of a fair coin? (If I were one of the players, I would be gone after the first round.) –  André Nicolas Jul 1 '13 at 4:26
    
I edited my question. The number of players is even and they are of equal ability. Sorry. –  please delete me Jul 1 '13 at 4:28
    
it looks like you need $2^n$ players, not $2n$ players. –  Yimin Jul 1 '13 at 4:36
    
I changed it but I don't see why it has to be $2^n$, doesn't the number of players only have to be even? –  please delete me Jul 1 '13 at 4:40
    
If six players entered, then there would be three players in the next round... –  Austin Mohr Jul 1 '13 at 4:40

3 Answers 3

up vote 2 down vote accepted

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} }$.

share|improve this answer
    
Nice answer! Saves a lot of time in exams :) –  please delete me Jul 1 '13 at 17:25

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.

share|improve this answer
    
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 1 '13 at 5: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 1 '13 at 5:22
    
Makes a lot of sense now! Thank you! –  please delete me Jul 1 '13 at 5:32
1  
You are welcome. Much less insightful, however, than Calvin Lin's answer! Indeed rather plodding. But works. –  André Nicolas Jul 1 '13 at 6:00

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.