Putnam 1996

Problem A3

There are six courses on offer. Each of 20 students chooses some all or none of the courses. Is it true that we can find two courses C and C' and five students S1, S2, S3, S4, S5 such that each Si has chosen C and C', or such that each Si has chosen neither C nor C'?



Answer: false.

Easy, once you have seen it!

A little experimentation suggests that if the result is false the choice of courses taken and not taken must be fairly balanced. This suggests taking the set S of all distinct subsets of 3 courses. |S| = 20, so we allocate one member of S to each student. Now there are 4 members of S containing any two given courses and 4 members of S not containing either of two given courses, so the assertion in the question is false.



Putnam 1996

© John Scholes
12 Dec 1998