, 2011

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.