What is the probability that player A and B play against each other? 
Players with same skill take part in a competition. The probability of
  winning each game is 0.5. At first, we divide a group of $2^n$ people
  to random pairs that play against each other. Then we will do the same
  for $2^{n-1}$ winners and this continues until there is only
  one winner. What is the probability that player A and B play against
  each other?

I know we should calculate the sum of probabilities that two players play against each other in the first round, then for second round and etc. So how can i calculate the probability that two players play at round K?
 A: *

*It is a knockout competition with $m=2^n$ players so $m-1$ knockouts or matches or parings are needed to produce a winner

*There are ${m \choose 2}=\frac{m(m-1)}{2}$ equally-likely possible parings of the $m$ players, so the probability any particular match involves both players A and B is  $\frac{2}{m(m-1)}$, and so the expected number of the $m-1$ matches which involve both players A and B is $(m-1) \times \dfrac{2}{m(m-1)}=\dfrac{2}{m}$

*Since players A and B can only meet $0$ or $1$ times, the probability they meet is $\dfrac{2}{m} = \dfrac{1}{2^{n-1}}$
A: *

*$P(A , B \text{ play at round } 1) = \frac{1}{2^{n-1}}$



When we have $2^{n}$ people, then we have at most $\log^{2^{n}}_{2}$ rounds. For example, assume we have only $2$ players, then $P(A , B \text{ play at round } 1) = \frac{1}{2^{\log^{2}_{2}-1}} = 1$



*

*$P(A , B \text{ play at round } 2) = P(A , B \text{ did not play at round } 1 \text{ and } A , B \text{ both win at the first round}) = (1-\frac{1}{2^{n-1}})(\frac{1}{2})^{2}$

*$P(A , B \text{ play at round } 3) = P(A , B \text{ did not play at round } 1,2 \text{ and } A , B \text{ both win at the first, second rounds}) = (1-\frac{1}{2^{n-1}})(1-\frac{1}{2^{n-2}})(\frac{1}{2})^{4}$
$$...$$


*

*$\forall k<n: \quad P(A , B \text{ play at round } k) = (\frac{1}{2})^{2(k-1)}\times \Pi_{i=1}^{k}(1-\frac{1}{2^{n-i}})$


$$...$$


*

*$\bbox[5px,border:2px solid #C0A000]{P(A , B \text{ play at round } n \text{ and } n>1) = (\frac{1}{2})^{2(n-1)}\times \Pi_{i=1}^{n-1}(1-\frac{1}{2^{n-i}})}$

A: Hmm...I don't see any real difference between this and an ordinary single-elimination tournament where the seeding is set from the start.  Maybe I'm missing something.
Anyway, assuming that there isn't any difference, we observe that Player A has $2^n-1$ different possible opponents in the first round.  Of those, $2^{n-1}$ are in the opposite half of the draw, and both they and Player A would have to win $n-1$ games to meet; this happens with probability $\frac{1}{4^{n-1}}$.  $2^{n-2}$ are in the same half, but opposite quarters, and both they and Player A would have to win $n-2$ games to meet; this happens with probability $\frac{1}{4^{n-2}}$.  And so on, until we get to the $2^{n-n} = 2^0 = 1$ single player who meets Player A in the first round.  Altogether, the probability of Player A and a given Player B meeting eventually is
\begin{align}
\frac{1}{2^n-1} \sum_{k=1}^n 2^{n-k}\frac{1}{4^{n-k}}
    & = \frac{1}{2^n-1} \sum_{k=1}^n \frac{1}{2^{n-k}} \\
    & = \frac{1}{2^n-1} \sum_{k=0}^{n-1} \frac{1}{2^k} \\
    & = \frac{1}{2^n-1} \left(2-\frac{1}{2^{n-1}}\right) \\
    & = \frac{1}{2^n-1} \times \frac{2^n-1}{2^{n-1}} \\
    & = \frac{1}{2^{n-1}}
\end{align}
I'll come back to edit this if I think (or someone points out) that there's a substantive difference between random reseeding and not reseeding.

There's also a pretty simple proof by induction: For $n = 1$ (two players), the probability is clearly $\frac{1}{2^n-1} = 1$.  For $n > 1$, the probability that they meet in the first round is $\frac{1}{2^n-1}$.  If they don't meet in the first round (with probability $\frac{2^n-2}{2^n-1}$), then they must both win their first games (with probability $\frac14$) to get to the next round.  With reseeding, this is clearly the case of $n-1$, so with the premise that the probability of them meeting at that point is $\frac{1}{2^{n-1-1}} = \frac{1}{2^{n-2}}$, the overall probability for case $n$ is
\begin{align}
\frac{1}{2^n-1}+\frac{2^n-2}{2^n-1} \times \frac14 \times \frac{1}{2^{n-2}}
    & = \frac{1}{2^n-1} \left(1+\frac{2^n-2}{2^n}\right) \\
    & = \frac{1}{2^n-1} \times \frac{2^{n+1}-2}{2^n} \\
    & = \frac{1}{2^n-1} \times \frac{2^n-1}{2^{n-1}} \\
    & = \frac{1}{2^{n-1}}
\end{align}
