This is almost the definition of a "$1$-factorization of $K_{2k}$", except that a $1$-factorization has an unordered set of matchings instead of a sequence of rounds. Since there are $2k-1$ rounds, this means that there are $(2k-1)!$ times as many tournaments, according to the definition above, as there are $1$-factorizations.
Counting $1$-factorizations of $K_{2k}$ seems to be a nontrival problem; see the Encyclopedia of Mathematics entry. The number of $1$-factorizations of $K_{2k}$ is OEIS sequence A000438. Also, see this paper (also here) for a count in the $k=7$ case.
Why the hint is required depends on the way you derived your result, not just on the result you post.
However, here's an alternative solution.
Denote
$$ p_{k,n}:=P(\text{Player #$k$ wins an $n$ round tournament}).$$
As a preliminary step, we should eliminate the cases $p=\frac12$ as then everything is symmetric, i.e. the probability that player #2 (or anybody else) wins, is exactly $\frac1n$. Similarly, if $p=1$, then #1 wins the tournament a.s., hence $p_{2,n}=0$. And if $p=0$, then the max player will win a.s., i.e. then $p_{2,n}=0$ except that $p_{2,1}=1$.
After these remarks, we don't get into trouble if we wish to divide by $p$, or $1-p$ or $1-2p$ below.
Next, let us compute the probability that player $1$ wins the tournament. To do so, he must survive the first round and then win a tournament of $2^{n-1}$ players among which he (after renumbering the players to fill the gaps without changing relative order) is still number one. Then we have
$$ p_{1,n}=\begin{cases}1&\text{if }n=0,\\
p\cdot p_{1,n-1}&\text{if }n>0,\end{cases}$$
In other words
$$p_{1,n}=p^n.$$
Now what about player $2$? To win, he must survive the first round; that is he
- either plays player #1 (with probaility $\frac1{2^n-1}$) and wins with probaility $1-p$, after which he is automatically the #1 of the remaining players
- or plays somebody else (with $1-\frac1{2^n-1}$) and wins with probability $p$. Player #1 also wins with porbability $p$, and then player #2 is still #2 of the remaining players
- or as before, but player #1 loses his match, so our #2 becomes #1 of the survivors.
That is, for $n>0$ (otherwise, a player #2 doesn't even participate) we have
$$\begin{align}p_{2,n}&=\frac1{2^n-1}\cdot(1-p)\cdot p_{1,n-1}+\left(1-\frac1{2^n-1}\right)\cdot\left( p^2\cdot p_{2,n-1}+ p\cdot (1-p)\cdot p_{1,n-1}\right)
\\&=\frac{p^{n-1}(1-p)}{2^{n}-1} +\frac{(2^{n}-2)(1-p)p^n}{2^{n}-1}+\frac{(2^{n}-2)p^2}{2^{n}-1}\cdot p_{2,n-1}.
\end{align}$$
(Note that this immediately gives $p_{2,1}=1-p$).
If we substitue $p_{2,n}=\frac{p^n}{2^n-1}(a_n+c)$, we obtain
$$ a_n +c= \frac{1-p}{p}+(2^n-2)(1-p)+2p(a_{n-1}+c),$$
hence by chosing $c=\frac{1-p}{p(1-2p)}$
$$ a_n = (2^n-2)(1-p)+2pa_{n-1}.$$
Note that $p_{2,1}=1-p$ implies $a_1=\frac{2(1-p)}{2p-1}$, so we can extend this to $a_0=\frac{1-p}{(2p-1)p}$.
Substitute again, $a_n=2^np^nb_n$, to find
$$ b_n = \frac{(2^n-2)(1-p)}{2^np^n}+b_{n-1}= (1-2^{1-n})\frac{(1-p)}{p^n}+b_{n-1}.$$
Hence
$$\begin{align} b_n &= b_0+\sum_{k=1}^n(1-2^{1-k})\frac{(1-p)}{p^k}\\&=b_0 + (1-p)\sum_{k=1}^np^{-k}-2(1-p)\sum_{k=1}^n(2p)^{-k}\\&
= b_0 + (p^{-n}-1) -2(1-p) \frac{(2p)^{-n}-1}{1-2p}\\
&= \frac1{p^{n}}-\frac{2(1-p)}{(1-2p)(2p)^n} +\left(b_0-1+\frac{2(1-p)}{1-2p}\right)
\\&=\frac1{p^{n}}-\frac{2(1-p)}{(1-2p)(2p)^n}-\frac1p\end{align}$$
Therefore,
$$ a_n = 2^n-\frac{2(1-p)}{1-2p}-2^np^{n-1}$$
and ultimately,
$$ p_{2,n} = \left(2^n-2^np^{n-1}+\frac{1-p}{p}\right)\frac{p^n}{2^n-1}.$$
Best Answer
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)}. $$