22. A round-robin tournament of $n$ contestants is one in which each of the

$\binom{n}{2}$ pairs of contestants play each other exactly once, with the outcome of any play being that one of the contestants wins and the other loses. For a fixed integer $k$, $k

$$\binom{n}{k}[1-(\frac{1}{2})^k]^{n-k}<1$$

then such an outcome is possible.

HINT: Suppose that the results of the games are independent and that each game is equally likely to be won by either contestant. Number the

$\binom{n}{k}$ sets of $k$ contestants, and let $B_i$ denote the event that no contestant beat all of the

$k$ players in the $i$th set. Then use Boole's inequality to bound $P(\bigcup_i B_i)$.