A round-robin tournament of n contestants is a tournament in which each of the
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
then such an outcome is possible.
Suppose that the results of the games are independent and that each game is equally likely to be won by either contestant. Number the
sets of k contestants, and let Bi denote the event that no contestant beat all of the k players in the ith set. Then use Boole’s inequality to bound

  • CreatedOctober 22, 2015
  • Files Included
Post your question