This exercise employs the probabilistic method to prove a result about round-robin tournaments. In a round-robin tournament with m players, every two players play one game in which one player wins and the other loses.
We want to find conditions on positive integers m and k with k A) Show that p(E¯¯¯¯)≤∑(mk)j=1p(Fj), where Fj is the event that there is no player who beats all k players from the jth set in a list of the (mk) sets of k players.
B) Show that the probability of Fj is (1−2−k)m−k.
C) Conclude from parts (a) and (b) that p(E¯¯¯¯)≤(mk)(1−2−k)m−k and, therefore, that there must be a tournament with the described property if (mk)(1−2−k)m−k<1.
D) Use part (c) to find values of m such that there is a tournament with m players such that for every set S of two players, there is a player who has beaten both players in S. Repeat for set of three players.