The probability of meeting in a tournament $2^n, n\in\mathbf N$ tennis players compete in a tournament. In the first round, they partition into a set of $2^{n-1}$ disjoint pairs. The two players in each pair compete against each other. The $2^{n-1}$ winners form a set of $2^{n-2}$ disjoint pairs and compete in the next round and so on. This competition lasts for $n$ rounds. The partition in each round is uniformly random. The players are strictly ranked and the higher ranked player always beats the lower one. The ranking is equally likely. For two chosen players, what is the probability that they will compete against each other in a pair? 

If any player in each pairing is equally likely to win, it is easier.
 A: I think it's still the case that each player is equally likely to win in every pairing.
In the first round, if Player A and Player B are matched, with Player A ranked above Player B, then there is another ranking that swaps their ranks and leaves all others the same. Since these rankings are in 1-1 correspondence and all rankings are equally likely, both Player A and Player B have a 50% chance to win.
In the second round, suppose Player C and Player D meet. Suppose further that Player C defeated Player A in round 1, and Player D defeated Player B in round 1. So $r(C)>r(A)$ and $r(D)>r(B)$ where $r(\cdot)$ denotes the rank of a player. We cannot necessarily swap the ranks of $C$ and $D$, because then we may end up with $r(C)<r(A)$ or $r(D)<r(B)$. However, we can swapt the ranks of $C$ and $D$, and the ranks of $A$ and $B$. This does not change the outcome of the first round, but it swaps who wins in the second round. 
Similarly, you can make this argument for all later rounds. In every case, each player is equally likely to win in any pairing.
A: Imagine all $2^n$ players with names Alice, Bob, Charlie and so on stay in line. Then they are given a blue card with a number from $1$ to $2^n$ which means their skill in game and a red card with a number from $1$ to $2^n$ which means their position in a tournament bracket.
Given a permutation of blue cards $p_b$ and a permutation of red cards $p_r$ we can calculate how the tournament will go. Or in other words, predict all $2^n-1$ pairing that will happen in the tournament.
Imagine this huge table with $N=(2^n!)^2$ rows (each row corresponds to a particular permutation $p_b$ and $p_r$) and $M=2^n-1$ columns (all predicted pairings for a given row). Is pair Alice-Bob is more frequent in this table than Alice-Charlie? Of course, no. Because for every row with particular cards of Bob and Charlie, there is a row with cards of Bob and Charlie swapped. Thus we conclude that every $k={2^n\choose 2}=2^{n-1}(2^n-1)$ pair of names has the same number of entries in the table.
Then what is the number $x$ of rows with a particular pair in it? Since pair cannot happen in the same row twice:
$$
x\times k=N\times M, \qquad x=\frac{NM}k
$$
What is the probability to pick one of those $x$ rows?
$$
p=\frac xN = \frac Mk = \frac{2^n-1}{2^{n-1}(2^n-1)}=2^{-(n-1)}.
$$
