its very easy . just notice that if two classes have the same number of students , then they have at max 1 student in common . with a simple double counting you can find out that the number of classes with exactly x students is at max C(n,2)/C(x,2) . so the number of classes is the sum of all these numbers and is smaller than (n-1)(n-1) .

Very interesting. Can you please explain how did you apply the double counting here? I'll be very grateful if you do : )

The number of pairs of students $a, b$ we can choose is $\binom{n}{2}$. Suppose there are $X$ classes with $x$ students in. Let $C$ be one such class. We can choose $\binom{x}{2}$ pairs of students from $C$. But any pair from $C$ we will not find in any other class, because we know the classes only share one student. So the number of pairs of students $a, b$ we can choose such that $a$ and $b$ share a class of size $x$ is exactly $X \binom{x}{2}$, but clearly this is not more than the total number of pairs we can choose without any restriction. So \[X \binom{x}{2} \leq \binom{n}{2},\] so \[X \leq \frac{\binom{n}{2}}{\binom{x}{2}}\]

Thank you for a detailed explanation.

After the double counting, how do you show they all add up to less than $(n-1)^2$?

$\sum_{x=2}^n \frac{1}{\binom{x}{2}} = 2\left(1-\frac{1}{n}\right)$. This is the most famous telescopic sum ever (in a slight disguise).

Another approach: Each pair of students can give us at most $n-1$ classes. If it gave us more, there would be two classes of the same size with a common pair. So all pairs of students can give us at most $ {(n-1)} \binom{n}{2} $ classes. But, in this manner we counted every $i$-sized class $ \binom{i}{2} $ times. This leads us to the expression : ${ {\frac{\binom{n}{2}}{\binom{2}{2}}} + {\frac{\binom{n}{2}}{\binom{3}{2}}} + ... + {\frac{\binom{n}{2}}{\binom{n}{2}}}} $, which gives exactly the upper bound.

I used the last technic, but I didn't know the result of this expression... From Darij it's the "most famous telescopic sum ever", but it didn't ring a bell at all to me.

A stronger bound is the number of classes can't exceed $\binom{n}{2}$. Solution. Let there be $k$ students. Let $T$ be the number of triples of the form $(student, student, \text{number of students in the class})$ where the two students is in the class with the specified number of students. We have $$k \leq T \leq \binom{n}{2}$$It's enough to show that $$\binom{n}{2}\leq (n-1)^2 \iff n \ge 2 \text{ or } n \leq 1$$

Let $A_k$ be number of classes with $k$ students. Note that each $2$ students can only participate in one of these clases so $\binom{n}{2} \ge \binom{k}{2} A_k$. Let $t$ be number of clases so we have $t = A_2 + ... + A_n$ so $t \le \binom{n}{2}(\frac{1}{\binom{2}{2}} + ... + \frac{1}{\binom{n}{2}}) = n(n-1)(1 - \frac{1}{2} + ... - \frac{1}{n}) = n(n-1)(\frac{n-1}{n}) = (n-1)^2$.

Solved with my dear friend cursed_tangent1434 Let there be $n_i$ classes with size $i$. Double count the number of pairs (student pair, class). We get the inequality: \[\binom{i}{2}\cdot n_i\leq \binom{n}{2}\]So, \[n_i\le\frac{\binom{n}{2}}{\binom{x}{2}}\]Then, note that the number of classes is at most: \[\sum_{i=2}^{n}n_i=\binom{n}{2}\sum_{i=2}^n\frac{1}{\binom{i}{2}} = (n-1)^2\]due to a simple telescopic summing. This concludes the proof. Remark. Kinda neat problem in my opinion, Iran MO/TST problems are so fun!