Putnam Pigeonhole principle problem regarding a 20 person college and 6 courses

Question

Question: A certain college has 20 students and offers 6 courses. Each student can enroll in any or all of the 6 courses, or none at all. Prove or disprove: there must exist 5 students and 2 courses, such that either all 5 students are in both courses, or all 5 students are in neither course.

What I have tried so far: I noticed that $\binom{6}{3} = 20$ which means that each students can pick 3 of the 6 courses.

However, from here I don't know how to proceed. Any hints would be highly appreciated.

Answer 1

The assertion is false. There are, as you saw, $\binom63=20$ ways to choose a set of $3$ of the $6$ courses. Suppose that each student chooses a different set of $3$ courses. Consider any particular pair of courses, say $C_1$ and $C_2$: there are just $4$ other courses, so there are precisely $4$ sets of $3$ courses containing both $C_1$ and $C_2$. Thus, there are only $4$ students taking both $C_1$ and $C_2$. And there are only $\binom43=4$ students taking $3$ of the other $4$ courses, so there are only $4$ students who are taking neither of $C_1$ and $C_2$. In short, for any pair of courses, there are just $4$ students taking both and $4$ students taking neither.

Answer 2

The conclusion is the same as the above: the assertion is false. But if you really want to link it to the Pigeonhole Principle, one way to approach the problem is as following.

Call a combination of two courses "paired" if a student chooses both of the two courses or neither of the two courses. Consider a particular student. Let the number of courses he's enrolled in be $k$, then the number of "paired" courses he chooses is $$\binom{k}{2} + \binom{6 - k}{2} = \frac{1}{2}k(k - 1) + \frac{1}{2}(6 - k)(5 - k) = k ^ 2 - 6k + 15 = (k - 3) ^ 2 + 6 \geq 6.$$ This means, for a total of 20 students in the (small!) college, there must be a total at least $20 \times 6 = 120$ "paired" choices made. Then, as there are 6 courses available, there are $\binom{6}{2} = 15$ selections of two courses. We can think of these selections as "boxes" and the $120$ total choices made as "balls". However, we must account for the fact that a selection of two courses can be both selected or both not selected by a student. So in fact there are $15 \times 2 = 30$ "boxes". Now, since $120 = 30 \times 4 + 0$, by the Pigeonhole Principle, it is not necessary that at least 5 "balls" will fall into the same "box". A counterexample can be constructed as in the previous solution. This is, I think, one way you could use Pigeonhole Principle? But a counterexample is definitely more efficient.