3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I am trying to teach myself probability. Just to clarify, not exactly a student looking for homework solutions - but still a student $\endgroup$ – user669083 Jan 23 '12 at 22:29
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Very elegant! $ $ $\endgroup$ – Rasmus Jan 24 '12 at 7:27
  • $\begingroup$ yes it seems to be most elegant one. $\endgroup$ – user669083 Jan 24 '12 at 16:15
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ probably you are at the right path but still not getting your solution. What is wrong with what Rasmus thought ? $\endgroup$ – user669083 Jan 23 '12 at 22:52
  • $\begingroup$ still stuck guys. Help please. $\endgroup$ – user669083 Jan 23 '12 at 23:02
  • $\begingroup$ 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... $\endgroup$ – user669083 Jan 24 '12 at 17:26
  • $\begingroup$ @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. $\endgroup$ – Henry Jan 24 '12 at 18:58
  • $\begingroup$ 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. $\endgroup$ – user669083 Jan 24 '12 at 21:52
2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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