Question

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 < 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 where F_j is the event that there is no player who beats all k players from the
j th set in a list of the mk sets of k players.
b) Show that the probability of F_j is (1−2 ^−k ) ^m−k
c) Conclude from parts (a) and (b) that  C(m,k)(1−2 ^−k ) ^m−k and, therefore, that there must
be a tournament with the described property if    C(m,k)(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 sets of three players.

Answer 1

This is not a gate oriented qus.however the things that are asked to be proved can be remembered to answer mcq