Out of 40 incoming freshmen, 25 are registered for CS 110, 30 are registered for CS 160, 35 are registered for Math 254, and 33 are registered for Econ 101. Prove that at least three students are registered for all four courses.
Asked
Active
Viewed 65 times
2
-
What have you done so far? – symmetricuser Oct 06 '14 at 20:08
-
@symmetricuser I was still debating whether I had to do this as a combinatorial proof or not, but I'm unsure. – user3434743 Oct 06 '14 at 20:12
1 Answers
2
Imagine that each course costs a student $\$1000$ in tuition fees.
If we calculate $25+30+35+33$, we see that the university raked in $123000$ dollars.
If $2$ or fewer people took $4$ courses, then the university would have raked in at most $(2)(4)(1000)+(38)(3)(1000)$ dollars. This is $122000$ dollars.
Remark: The argument is a typical Pigeonhole Principle argument. Instead of thinking in money terms, one could identify the pigeonholes and the pigeons.
André Nicolas
- 507,029