Maths Olympiad Prep

Library / /18 of 120

Combinatorics Difficulty 4.8 AIME Prove it Croatia

Let NN and KK be positive integers. A number of students is first divided into NN non-empty groups and then the same students are divided into N+KN + K non-empty groups. Prove that in the second distribution at least K+1K+1 students are in a smaller group than in the first distribution. (Yugoslavia 1981)

Solution

Let SS be the set of all students. For sSs \in S we denote by asa_s the number of students in the group of the student ss in the first distribution and by bsb_s the number of students in the group of student ss in the second distribution.
We have
sS1as=N,sS1bs=N+K. \sum_{s \in S} \frac{1}{a_s} = N, \quad \sum_{s \in S} \frac{1}{b_s} = N + K.
Hence the sum of differences of numbers assigned to each student is equal to
sS(1bs1as)=K. \sum_{s \in S} \left( \frac{1}{b_s} - \frac{1}{a_s} \right) = K.
Since 1bs1as<1\left| \frac{1}{b_s} - \frac{1}{a_s} \right| < 1 it follows that for at least K+1K + 1 students we have 1bs1as>0\frac{1}{b_s} - \frac{1}{a_s} > 0, i.e. bs<asb_s < a_s.

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.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.