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?

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}
