Solved: This exercise employs the probabilistic method to

Chapter 6, Problem 6.2.39

(choose chapter or problem)

This exercise employs the probabilistic method to prove a result about round-robin tournaments. In a roundrobin 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 < m such that it is possible for the outcomes of the tournament to have the property that for every set of k players, there is a player who beats every member in this set. So that we can use probabilistic reasoning to draw conclusions about round-robin tournaments, we assume that when two players compete it is equally likely that either player wins the game and we assume that the outcomes of different games are independent. Let E be the event that for every set S with k players, where k is a positive integer less than m, there is a player who has beaten all k players in S. a) Show that peE) :s 2:21 p(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 (7) 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) :S (7)(1 - 2-k)m-k and, therefore, that there must be a tournament with the described property if (7)C1 - 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 sets of three players.