A competition is formatted such that every possible pair of participants compete against each other in a 1 vs. 1 match where there is always a winner and loser. There are a total of 2^n participants enrolled in the competition, where $n \in \mathbb{N}$.
Prove that at the end of the competition, there exists a group of $n+1$ participants $P_1, P_2, . . . , P_{n+1}$ such that for any integers $1 \le i < j \le n + 1$, we have that $P_i$ beat $P_j$.
[The question has been edited, rendering the following argument moot. When posted, the question had $2n$ participants instead of $2^n$]
It's not true.
Assign the results of each match by flipping a coin. There are $(2n)(2n-1)\cdots n$ ways to choose $n+1$ participants $P_1,P_2,\dots,P_{n+1}$ in order. If $P_i$ beat $P_j$ whenever $i < j$, then that determines the results of all $\binom{n}{2}$ matches among them. This happens with probability $2^{-n(n-1)/2}$.
So then, the expected number of lists of $n+1$ participants ordered by their match results in this way is $2^{-n(n-1)/2}\cdot \frac{(2n)!}{(n-1)!}$. For $n\ge 10$, this is less than $1$. If something with nonnegative integer values has average less than $1$, it has to be zero sometimes, and that means there are competition results that don't have such a list.
