Exercise 6.1
Six musicians gathered at a music festival. At each concert some musicians played in the concerts while the others listened, as part of the audience. What is the least number of concerts needed to be scheduled in order that each musician may listen, as part of the audience, to every other musician.
Full disclosure: I still don't know what TT means by the 'point-scoring' hint he gives. I guess in a way you could call what I'm about to do scoring, but it's not as creative as I feel like point scoring usually is. So we are going to convert this problem into another shape - bear with me. Each concert selects a group of musicians as listeners. Note that each musician then sees every musician not in that group on the stage. Thus for a musician \( m \) to have seen every other on stage, they need to be in a set of groups \( G_m \) such that for every other musician, \( m' \) there is some \( g \in G_m \) s.t. \( m' \notin g \). Or equivalently, the intersection of groups containing \( m \) must only contain \( m \).
First a simpler case: one can quickly check that 3 musicians require 3 groups. Next we check that 4 musicians require 4 groups. First, a group of size 1 would reduce us to the 3 musician and 3 group case (giving us a total of 4 groups again), while using a group of size 3 would require the 3 musicians contained within to again be split with 3 groups (so 4 groups total). Meanwhile using only groups of size 2, and less than 4 groups would give us ( 4 musicians ) ( # average groups per musician ) = ( # groups ) ( 2 musicians per group ) < 8 \( \rightarrow \) # average groups per musician \( < 2 \), so there must be some musician with only 1 group, and then that group must be of size 1. A contradiction. So 6 musicians would require at least 4 concerts, and indeed it turns out this is sufficient. Given musicians labelled \( a \) through \( f \) we can use groups \( (a, b, f) \), \( (b, c, d) \), \( (d, e, f) \), \( ( a, c, e ) \). The reader can check the intersections work as desired. \( \blacksquare \)