Maths Olympiad Prep

Library / /82 of 155

Combinatorics Difficulty 6.2 National olympiad Prove it Saudi Arabia

In a school, there are totally nn students, with n2n \geq 2. The students take part in mm clubs and in each club, there are at least 22 members (a student may take part in more than 11 club). Eventually, the Principal notices that: If 22 clubs share at least 22 common members then they have different numbers of members. Prove that
m(n1)2. m \leq (n-1)^2.

Solution

Let aia_i be the number of clubs that have ii members. Here, 2in2 \leq i \leq n and
m=a2+a3++an. m = a_2 + a_3 + \cdots + a_n.
We will count the tuples (A,B,C)(A, B, C) in which the students A,BA, B take part in the same club CC that has ii members.

1. The first way of counting:
- Choosing 11 club among the clubs that have ii members, we have aia_i ways.
- Choosing 22 students that take part in that club, we have (i2)\binom{i}{2} ways.

2. The second way of counting:
- Choosing 22 students among all students of the school, we have (n2)\binom{n}{2} ways.
- Choose 11 club in which these two students take part. By assumption, there is at most 11 such club.

So we get the following relation:
ai(i2)(n2)ai(n2)(i2). a_i \binom{i}{2} \leq \binom{n}{2} \Leftrightarrow a_i \leq \frac{\binom{n}{2}}{\binom{i}{2}}.
Hence, we have
m=a2+a3++an(n2)(1(22)+1(32)++1(n2)). m = a_2 + a_3 + \cdots + a_n \leq \binom{n}{2} \left( \frac{1}{\binom{2}{2}} + \frac{1}{\binom{3}{2}} + \cdots + \frac{1}{\binom{n}{2}} \right).
Note that
i=2n1(i2)=i=2n2i(i1)=2i=2n(1i11i)=2(11n)=2(n1)n. \sum_{i=2}^{n} \frac{1}{\binom{i}{2}} = \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,
mn(n1)22(n1)n=(n1)2. m \leq \frac{n(n-1)}{2} \cdot \frac{2(n-1)}{n} = (n-1)^2.
\square

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 and solution reproduced as published; topic and difficulty added by this site.