0) As a preliminary result, show by induction that for events E1,E2,,EM, P(E1orE2ororEM)m=1MP(Em). But BagelBot could not neglect its responsibilities as now head of MagusCorp, and resolved to do something about flagging morale and general confusion following the disappearance of the CEO and major executives. BagelBot decided that what people needed was a friendly competition, a tournament to decide the best bagel spread of all time. Given two different spreads, people could vote on the better one, and ultimately the Champion Bagel Spread would be determined. BagelBot realizes suddenly that if every spread competes against every other spread - there may not actually be a champion spread at all. 1) Representing a tournament on N bagel spreads as a directed graph on N vertices (an edge ab exists if a beats b ), give an example where every spread is beaten by some spread. BagelBot considers, however, maybe there is a pair of bagel spreads that, when taken together, at least one of them beats every other spread in the tournament. 2) Show that BagelBot is wrong - give an example a tournament where for every pair of spreads, there is some other spread that beats them both. Hint: The smallest such N where this is possible is at most 10 . At this point, having never heard of bracketing, BagelBot experiences a flash of panic. Is March ruined? Maybe enlarging this winning set would do it - maybe a k-set winner could be a set of k spreads, where for any other spread, at least one of the k-spreads beats that spread. The previous example shows that a 2-set winner doesn't have to exist. What about a 3-set winner? What k values might work? BagelBot resolves to test this. Consider generating a tournament on n bagel spreads by settling each competition by fair coin flip. 3) For a given set S of k-many spreads, what's the probability that a given spread s not in S beats everything in S? 4) For a given set S of k-many spreads, what's the probability that no spread outside of S beats everything in S ? 5) Using 3.0 and 3.4, give a bound on the probability that, for this randomly generated tournament on n bagel spreads, there exists a k-set winner. 6) Give a condition on n and k that guarantees there is a tournament with no k-set winner. 7) Given the condition in 3.6, what's the smallest n that guarantees there is a tournament with no 2-set winner? If there is a discrepancy between this number and what you got in 3.2 , why? 8) Show that in fact BagelBot's plans are in trouble, and that for any k, there are tournaments with no k-set winners for all sufficiently large n. 9) In fact, show that taking klog2(n) for 0