Putnam 1996, Problem A-3

Suppose that each of 20 students has made a choice of anywhere from 0 to 6 courses from a total of 6 courses offered. Prove or disprove: there are 5 students and 2 courses such that all 5 have chosen both courses or all 5 have chosen neither course.

Solution:
The claim is false. There are \(\binom{6}{3} = 20\) ways to choose 3 of the 6 courses; have each student choose a different set of 3 courses. Then each pair of courses is chosen by 4 students (corresponding to the four ways to complete this pair to a set of 3 courses) and is not chosen by 4 students (corresponding to the 3-element subsets of the remaining 4 courses).  

Note: Assuming that no two students choose the same courses, the above counterexample is unique (up to permuting students). This may be seen as follows: Given a group of students, suppose that for any pair of courses (among the six) there are at most 4 students taking both, and at most 4 taking neither. Then there are at most \(120 = (4 + 4)\binom{6}{2}\) pairs \((s, p)\), where \(s\) is a student, and \(p\) is a set of two courses of which \(s\) is taking either both or none. On the other hand, if a student \(s\) is taking \(k\) courses, then he/she occurs in \(f(k) = \binom{k}{2} + \binom{6 - k}{2}\) such pairs \((s, p)\). As \(f(k)\) is minimized for \(k = 3\), it follows that every student occurs in at least \(6 = \binom{3}{2} + \binom{3}{2}\) such pairs \((s, p)\). Hence there can be at most \(120/6 = 20\) students, with equality only if each student takes 3 courses, and for each set of two courses, there are exactly 4 students who take both and exactly 4 who take neither. Since there are only 4 ways to complete a given pair of courses to a set of 3, and only 4 ways to choose 3 courses not containing the given pair, the only way for there to be 20 students (under our hypotheses) is if all sets of 3 courses are in fact taken. This is the desired conclusion.  

However, Robin Chapman has pointed out that the solution is not unique in the problem as stated, because a given selection of courses may be made by more than one student. One alternate solution is to identify the 6 courses with pairs of antipodal vertices of an icosahedron, and have each student pick a different face and choose the three vertices touching that face. In this example, each of 10 selections is made by a pair of students.