3
$\begingroup$

In a tournament of $2^n$ players, Alice and Beatrice ask what's the probability that they'll not compete if they've the same level of play?

Let :

  • $A_i$ : Alice plays the $i$-th tournament ;
  • $B_i$ : Beatrice plays the $i$-th tournament ;
  • $E_i$ : Alice and Beatrice don't compete at the $i$-th tournament.

For the moment, I was only able to calculate $$P(A_i) = \left(\frac{1}{2}\right)^{n-1} \quad \forall^{\;i}_{\; 1 \dots n}$$

Can you give me a hint?

$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

Hints:

Assuming every result is equally probable,

  • How many contests are there? (All but one of the competitors need to be knocked out)

  • How many potential pairings are there?

  • What proportion of potential pairings actually meet in a contest? Can you simplify this?

$\endgroup$
4
  • $\begingroup$ I think there's $2^{n-1}$ contest. I suppose there's $\binom{2^n}{2}$ initial pairs possibles. But I doesn't understand your third point. Can you explain? $\endgroup$
    – hlapointe
    Feb 2, 2016 at 0:23
  • $\begingroup$ @hlapointe: There are $2^n-1$ contests, as all but one must be knocked out, not $2^{n-1}$. As you say there are ${2^n \choose 2}$ initial pairs possible, but it might be helpful to write this as $\dfrac{2^n(2^n-1)}{2}= 2^{n-1}(2^n-1)$. Divide the former by the latter and you get $\dfrac{1}{2^{n-1}}$ as the probability of Alice and Beatrice meeting. $\endgroup$
    – Henry
    Feb 2, 2016 at 13:51
  • $\begingroup$ Ok. But can you explain the logic behind your steps because I don't really understand why that works?!. $\endgroup$
    – hlapointe
    Feb 2, 2016 at 14:37
  • 1
    $\begingroup$ There are $2^{n-1}(2^n-1)$ possible pairs and they are equally probable so the probability one given contest is Alice v. Beatrice is $\dfrac{1}{2^{n-1}(2^n-1)}$. In fact there are $2^n-1$ contests and none of them are repeat pairings, so the probability any of them are Alice v. Beatrice is $(2^n-1) \times \dfrac{1}{2^{n-1}(2^n-1)}$ $\endgroup$
    – Henry
    Feb 2, 2016 at 14:44
0
$\begingroup$

Hint:

[ Note that A and B here do not necessarily stand for Alice and Beatrice ]

A -----
       |-------- A ------
B ------                |
                        |---- D ----------
C -----                 |                 |
       |-------- D ------                 |
D ------                                  |
                                          |------ D
E -----                                   |
       |-------- F ------                 |
F -----                |                  |
                       |---- F ----------
G -----                |
       |-------- G ----
H ----
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .