SAUDI ARABIAN MATHEMATICAL COMPETITIONS

Let $a_i$ be the number of clubs that have $i$ members. Here, $2\le i\le n$ and $$m=a_2+a_3+\cdots +a_n.$$ We will count the tuples $(A,B,C)$ in which the students $A,B$ take part in the same club $C$ that has $i$ members.

1. The first way of counting: - Choosing $1$ club among the clubs that have $i$ members, we have $a_i$ ways. - Choosing $2$ students that take part in that club, we have $\left(\genfrac{}{}{0ex}{}{i}{2}\right)$ ways.

2. The second way of counting: - Choosing $2$ students among all students of the school, we have $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ ways. - Choose $1$ club in which these two students take part. By assumption, there is at most $1$ such club.

So we get the following relation: $$a_i\left(\genfrac{}{}{0ex}{}{i}{2}\right)\le \left(\genfrac{}{}{0ex}{}{n}{2}\right)\iff a_i\le \frac{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}{\left(\genfrac{}{}{0ex}{}{i}{2}\right)}.$$ Hence, we have $$m=a_2+a_3+\cdots +a_n\le \left(\genfrac{}{}{0ex}{}{n}{2}\right)\left(\frac{1}{\left(\genfrac{}{}{0ex}{}{2}{2}\right)}+\frac{1}{\left(\genfrac{}{}{0ex}{}{3}{2}\right)}+\cdots +\frac{1}{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}\right).$$ Note that $$\sum _{i=2}^n\frac{1}{\left(\genfrac{}{}{0ex}{}{i}{2}\right)}=\sum _{i=2}^n\frac{2}{i(i-1)}=2\sum _{i=2}^n\left(\frac{1}{i-1}-\frac{1}{i}\right)=2\left(1-\frac{1}{n}\right)=\frac{2(n-1)}{n}.$$ Therefore, $$m\le \frac{n(n-1)}{2}\cdot \frac{2(n-1)}{n}=(n-1{)}^2.$$ $\square$