Chapter 3, Problem 3.24TE

A round-robin tournament of n contestants is a tournament in which each of the $\left(\begin{array}{c}n\\ 2\end{array}\right)$ 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<n$, a question of interest is whether it is possible that the tournament outcome is such that for every set of k players, there is a player who beat each member of that set. Show that if $\left(\begin{array}{c}n\\ k\end{array}\right){\left[1-{\left(\frac{1}{2}\right)}^k\right]}^{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 $\left(\begin{array}{c}n\\ k\end{array}\right)$ sets of k contestants, and let $B_i$ denote the event that no contestant beat all of the k players in the ith set. Then use Boole’s inequality to bound $P\left({\displaystyle \underset{i}{\cup }{B}_i}\right)$.