South-Afrika, 2011

Combinatorics Difficulty 5.3 AIME, harder Prove it South Africa

A school has $n$ students and there are some extra classes provided for them so that each student can participate in any number of them. We know that there are at least two participants in any class. We also know that if two different classes have two common students, then the numbers of their participants are different. Prove that the total number of classes is not greater than $(n - 1)^2$ .

Solution

Let $A_i$ , $2 \le i \le n$ , be the set of all classes with $i$ participants. We will show that $|A_i| \le \frac{n(n-1)}{i(i-1)}$ . Since every pair of students is together in at most one class of each $A_i$ , we have that $\binom{i}{2} |A_i| \le \binom{n}{2}$ , giving
$|A_i| \le \frac{\binom{n}{2}}{\binom{i}{2}} = \frac{n(n-1)}{i(i-1)}.$
Now, the total number of classes equals
$\begin{aligned} & |A_2| + |A_3| + \dots + |A_n| \\ & \le n(n-1) \left( \frac{1}{2(2-1)} + \frac{1}{3(3-1)} + \dots + \frac{1}{n(n-1)} \right) \\ & = n(n-1) \left( 1 - \frac{1}{n} \right) = (n-1)^2, \end{aligned}$
as required.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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