Tuesday, May 5, 2015

Problem #1


Let m_i be a member indexed by i which is an element of {1,2,3,4...20} and let each game have two spots s_1 and s_2. Let A be the set such that it contains members that play in at least one or more games and are found in s_1 and let B be the set such that it contains members that play in at least one or more games and are found in s_2. Let the union of A and B be the empty set.

We show that the set A has to at least have |A| greater than or equal to 6.

If |A| is less than or equal to 5, then not all members play at least one game. Since this will only allow at most 14 members in s_2 which means that there will be one or more player that does not play at all.

Thus, |A| is greater than or equal to 6.

Since |A| is greater than or equal to 6, there will be 6 or more members in s_1 and thus |B| =  (20 - |A|) members in s_2. Thus, there will be at least 6 games with distinct members in s_1.

If |A| = 6 then |B| = 14 and 14 distinct members in s_2 and thus 12 distinct players.
If |A| = 7 then |B| = 13 and 13 distinct members in s_2 and thus 12 or more distinct players.

Similarly WLOG when |A| greater than or equal to 10.

Thus, for every schedule there is at least a set of 6 games with 12 distinct players.