, 2017

Solution:

We make the following claim: if there is a 5-cycle (a directed cycle involving 5 players) in the tournament, then there is a 4-cycle.

Proof: Assume that $A$ beats $B$, $B$ beats $C$, $C$ beats $D$, $D$ beats $E$ and $E$ beats $A$. If $A$ beats $C$ then $A, C, D, E$ forms a 4-cycle, and similar if $B$ beats $D$, $C$ beats $E$, and so on. However, if all five reversed matches occur, then $A, D, B, C$ is a 4-cycle.

Therefore, if there are no 4-cycles, then there can be only 3-cycles or no cycles at all.

Case 1: There is a 3-cycle. Assume that $A$ beats $B$, $B$ beats $C$, and $C$ beats $A$. (There are $\binom{5}{3}=10$ ways to choose the cycle and 2 ways to orient the cycle.) Then $D$ either beats all three or is beaten by all three, because otherwise there exists two people $X$ and $Y$ in these three people such that $X$ beats $Y$, and $D$ beats $Y$ but is beaten by $X$, and then $X, D, Y, Z$ will form a 4-cycle ($Z$ is the remaining person of the three). The same goes for $E$. If $D$ and $E$ both beat all three or are beaten by all three, then there is no restriction on the match between $D$ and $E$. However, if $D$ beats all three and $E$ loses to all three, then $E$ cannot beat $D$ because otherwise $E, D, A, B$ forms a 4-cycle. This means that $A, B, C$ is the only 3-cycle in the tournament, and once the cycle is chosen there are $2 \cdot 2 + 2 \cdot 1 = 6$ ways to choose the results of remaining matches, for $10 \cdot 2 \cdot 6 = 120$ ways in total.

Case 2: There are no cycles. This means that the tournament is a complete ordering (the person with a higher rank always beats the person with a lower rank). There are $5! = 120$ ways in this case as well.

Therefore, the probability of not having a 4-cycle is $\frac{120+120}{2^{10}} = \frac{15}{64}$, and thus the answer is $1 - \frac{15}{64} = \frac{49}{64}$.