Let and be positive integers. A number of students is first divided into non-empty groups and then the same students are divided into non-empty groups. Prove that in the second distribution at least students are in a smaller group than in the first distribution. (Yugoslavia 1981)
Solution
Let be the set of all students. For we denote by the number of students in the group of the student in the first distribution and by the number of students in the group of student in the second distribution.
We have
Hence the sum of differences of numbers assigned to each student is equal to
Since it follows that for at least students we have , i.e. .
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.