1998 IMO Problems/Problem 2

Problem

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

Solution

This problem needs a solution. If you have a solution for it, please help us out by adding it.

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

\begin{align*} {c_i \choose 2} + {{b - c_i} \choose 2} &= \frac{1}{2}\left(c_i(c_i - 1) + (b - c_i)(b - c_i - 1) \right) \\ &= \frac{1}{2}\left( c_i^2 + (b - c_i)^2 - b \right) \\ &\geq \frac{1}{2}\left( \frac{b^2}{2} - b \right) \\ &= \frac{b^2 - 2b}{4} \end{align*}

where the inequality follows from AM-QM. Since $b$ is odd, $b^2 - 2b$ is not divisible by $4$ and we can improve 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.$

Let $N$ stand for the number of instances where two judges agreed on a candidate. Since there are $a$ candidates, it follows that

$N = \sum_{i = 1}^n {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 {b - 1}{2b}.$

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

Page

Toolbox

Search

1998 IMO Problems/Problem 2

Problem

Solution

See Also