1998 IMO Problems/Problem 2

Problem

In a competition, there are $a$ contestants and $b$ judges, where $b\ge3$ is an odd integer. Each judge rates each contestant as either “pass” or “fail”. Suppose $k$ is a number such that, for any two judges, their ratings coincide for at most $k$ contestants. Prove that $\frac{k}{a}\ge\frac{b-1}{2b}$.

Solution

Let $c_i$ stand for the number of judges who pass the $i$th candidate. The number of pairs of judges who agree on the $i$th contestant is then given by

(ci2)+(bci2)=12(ci(ci1)+(bci)(bci1))=12(ci2+(bci)2b)12(b22b)=b22b4

where the inequality follows from AM-QM. Since $b$ is odd, $b^2 - 2b$ is not divisible by $4$ and we can strengthen the inequality to

\[{c_i \choose 2} + {{b - c_i} \choose 2} \geq \frac{b^2 - 2b + 1}{4} = \left(\frac{b - 1}{2}\right)^2.\]

Letting $N$ stand for the number of instances where two judges agreed on a candidate, it follows that

\[N = \sum_{i = 1}^a {c_i \choose 2} + {{b - c_i} \choose 2} \geq a \cdot \left( \frac{b - 1}{2} \right)^2.\]

The given condition on $k$ implies that

\[N \leq k \cdot {b \choose 2} = \frac{kb(b - 1)}{2}.\]

Therefore

\[a \cdot \left( \frac{b - 1}{2} \right)^2 \leq \frac{kb(b - 1)}{2},\]

which simplifies to

\[\frac{k}{a} \geq \frac{b - 1}{2b}.\]

See Also

1998 IMO (Problems) • Resources
Preceded by
Problem 1
1 2 3 4 5 6 Followed by
Problem 3
All IMO Problems and Solutions