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.

Suppose that we have a tennis tournament with 32 players. Players are matched in a completely random fashion, and we assume that each player always has probability 1/2 to win a match. What is the probability that two given players meet each other during the tournament.

share|improve this question
    
I am trying to teach myself probability. Just to clarify, not exactly a student looking for homework solutions - but still a student –  user669083 Jan 23 '12 at 22:29

3 Answers 3

up vote 4 down vote accepted

Easy general answer for $n$ players in a knockout tournament (and here $n=32$):

There are $\dfrac{n(n-1)}{2}$ potential pairs for matches.

To have one winner, $n-1$ players must be knocked out, so there are $n-1$ actual matches.

So the probability that a particular pair actually have a match is $\dfrac{n-1}{{n(n-1)/2}} = \dfrac{2}{n}$.

share|improve this answer
    
Very elegant! $ $ –  Rasmus Jan 24 '12 at 7:27
    
yes it seems to be most elegant one. –  user669083 Jan 24 '12 at 16:15

Hint 1: Consider the number of other players a particular player meets with what probability: one other with probability $1/2$; two others with probability $1/4$; three others with probability $1/8$; etc.

Hint 2: What is the expected number of other players a particular player meets?

Hint 3: How does Hint 2 relate to the original question?

Answer: $$ \dfrac{1 \times \dfrac{1}{2} + 2 \times \dfrac{1}{2^2} + 3 \times \dfrac{1}{2^3} + 4 \times \dfrac{1}{2^4} + 5 \times \dfrac{1}{2^4}}{31} = \dfrac{1}{16}$$

share|improve this answer
    
probably you are at the right path but still not getting your solution. What is wrong with what Rasmus thought ? –  user669083 Jan 23 '12 at 22:52
    
still stuck guys. Help please. –  user669083 Jan 23 '12 at 23:02
    
Shouldn't his expected number of players be 1*1+2*1/2+3*1/4+4*1/8+5*1/16. Because he definitely meets one person in first round. He meets the second person with a probability of half and so on... –  user669083 Jan 24 '12 at 17:26
    
@user669083: He cannot go further than the 5th round because the tournament is over, so the probability of finishing in the 5th round is $1/2^4$ rather than the $1/2^5$ it would be if there were further rounds. –  Henry Jan 24 '12 at 18:58
    
not exactly what I asked. I said he is definitely meeting one in round one. So probability of that should be 1 not 1/2, then same with meeting 2 people should be half. If he reaches 2nd round, he will meet two people by then. Your answer is correct. I am just trying to increase my understanding. –  user669083 Jan 24 '12 at 21:52

I get $$ \frac{1}{31} +\frac{30}{31}\frac{1}{4}\left(\frac{1}{15} +\frac{14}{15}\frac{1}{4}\left(\frac{1}{7} +\frac{6}{7}\frac{1}{4}\left(\frac{1}{3} +\frac{2}{3}\frac{1}{4}\right)\right)\right) $$ which equals $\dfrac{1}{16}=6.25\%$. Not sure if this is the most elegant solution, though.

share|improve this answer
    
I thought the same but the answer is 1/16 ? –  user669083 Jan 23 '12 at 22:48
    
@user669083: You are right. I just forgot the factor $\frac{2}{3}$. –  Rasmus Jan 23 '12 at 23:01
    
See my later answer for a more general and less arithmetic solution. –  Henry Jan 23 '12 at 23:42

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.