There are 14 students who have participated in a 3 hour test consisting of 15 short problems. Each student has solved a different number of problems and each problem has been solved by a different number of students. Prove that there exists a student who has solved exactly 5 problems.
Solution
Because there are 14 students, the possible numbers of students solving a problem are . Because there are 15 problems and each problem has been solved by a different number of students, there is a problem which has been solved by all the 14 students and another problem which has not been solved by any of the 14 students.
If we cancel both problems, the one solved by all the students and the one not solved by any of the students, we still have that each of the 14 students has solved a different number of the 13 remaining problems. But from these 13 remaining problems, the possible number of problems that a student has solved are . Again, because there are 14 students and each student has solved a different number of problems, there is a student who has solved exactly 4 problems from these 13 remaining problems. But this student has also solved the canceled problem solved by all the students and has not solved the canceled problem which has not been solved by any of the students. Therefore, this student has solved exactly 5 problems.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.