IMO 1998 · Problem 2

In a competition, there are \(a\) contestants and \(b\) judges, where \(b \geq 3\) 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 \(k/a \geq (b - 1)/(2b)\).

Official text of the problem. Official problem paper (PDF)

Solution

Let \(N\) be the number of pairs consisting of a contestant and an unordered pair of judges whose ratings of that contestant coincide. We count \(N\) in two ways.

There are \(\binom{b}{2}\) pairs of judges, and each pair agrees on at most \(k\) contestants. Hence \[ N\leq k\binom{b}{2}=\frac{kb(b-1)}2. \]

Now fix a contestant, and suppose exactly \(p\) judges give that contestant a “pass”. The other \(b-p\) judges give a “fail”, so the number of pairs agreeing on this contestant is \[ \frac{p(p-1)}2+\frac{(b-p)(b-p-1)}2 =\frac{(2p-b)^2+b^2-2b}{4}. \] Since \(b\) is odd, \(2p-b\) is an odd integer and therefore \((2p-b)^2\geq1\). Thus each contestant contributes at least \[ \frac{1+b^2-2b}{4}=\frac{(b-1)^2}{4} \] to \(N\). Summing over all \(a\) contestants gives \[ N\geq\frac{a(b-1)^2}{4}. \]

Combining the bounds, \[ \frac{a(b-1)^2}{4}\leq\frac{kb(b-1)}2. \] Dividing by the positive quantity \(ab(b-1)/2\), we obtain \[ \boxed{\frac{k}{a}\geq\frac{b-1}{2b}}. \]

The solution was checked against Evan Chen's published IMO solution notes.