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'?
Solution
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.
© John Scholes
jscholes@kalva.demon.co.uk
12 Dec 1998