# Alice, Beatrice and a tournament

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?

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?

• 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? Feb 2, 2016 at 0:23
• @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. Feb 2, 2016 at 13:51
• Ok. But can you explain the logic behind your steps because I don't really understand why that works?!. Feb 2, 2016 at 14:37
• 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)}$ Feb 2, 2016 at 14:44

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