IMO 1998 Problem 2

Proposed by: -
Verified: yes
Verdicts: PASS + PASS
Solve time: 4m11s

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}$.

Exploration

For each contestant, the pattern of ratings by the $b$ judges can be encoded by a binary vector of length $b$, where $1$ represents a pass and $0$ represents a fail. For two judges, their coincidence on a contestant corresponds to whether the corresponding coordinates of this vector are equal.

The condition in the problem restricts, for every pair of judges, how often their coordinates agree across all contestants. This suggests a global double counting over all pairs of judges and all contestants.

A natural quantity to study is, for a fixed contestant, how many pairs of judges agree on that contestant. If a contestant has $r$ passes, then the number of agreeing judge pairs contributed by this contestant depends only on $r$. Summing over all contestants converts the problem into an inequality involving a function of $r$ summed over all contestants.

The key difficulty is identifying the correct lower bound on this function, because the direction of the final inequality requires converting an upper bound on pairwise agreements into a lower bound on $k$.

The most promising strategy is to show that for every possible $r$, the number of agreeing pairs among judges is at least a fixed constant depending only on $b$, minimized when the split between passes and fails is as balanced as possible. This suggests analyzing a quadratic function in $r$ and locating its minimum.

Problem Understanding

There are $a$ contestants and $b$ judges, with $b$ an odd integer at least $3$. Each judge assigns either pass or fail to each contestant. For any pair of judges, the number of contestants on which their ratings coincide is at most $k$.

The goal is to prove the inequality

$\frac{k}{a} \ge \frac{b-1}{2b}.$

This is a Type B problem, meaning a pure proof is required.

The structure of the problem suggests converting pairwise constraints between judges into a global constraint over all contestants. The core difficulty lies in relating local pairwise agreement bounds to a uniform lower bound on $k$ via a double counting argument.

The quantity $k$ measures the maximum overlap of agreement between any two judges. The claim states that this overlap must be relatively large compared to $a$, with a precise threshold determined by $b$.

Proof Architecture

The proof introduces a function $f(r)$ defined as the number of agreeing pairs of judges on a contestant whose number of passes is $r$.

The first lemma states that for a contestant with $r$ passes among $b$ judges, the number of agreeing judge pairs on that contestant equals

$f(r) = \binom{r}{2} + \binom{b-r}{2}.$

The second lemma states that for odd $b$, the function $f(r)$ attains its minimum value at $r = \frac{b-1}{2}$ or $r = \frac{b+1}{2}$, and this minimum equals $\frac{(b-1)^2}{4}$.

The third lemma states that summing $f(r)$ over all contestants equals the total number of pairs of judges multiplied by the number of contestants on which they agree.

The final step combines these facts to derive a lower bound on $k$.

The most delicate point is the identification of the correct extremal value of $f(r)$ and ensuring that it is a global minimum over integers.

Solution

Lemma 1

For a fixed contestant, if $r$ judges assign pass and $b-r$ assign fail, then the number of unordered pairs of judges who agree on that contestant equals

$f(r) = \binom{r}{2} + \binom{b-r}{2}.$

The first term counts pairs of judges who both assign pass, and the second counts pairs who both assign fail. These cases are disjoint and exhaustive because any agreeing pair must either both lie in the pass set or both lie in the fail set.

This establishes a complete decomposition of agreement pairs for a single contestant.

Lemma 2

For odd $b$, write $b = 2m+1$. For a contestant with $r$ passes, define

$f(r) = \binom{r}{2} + \binom{b-r}{2}.$

Expanding,

$f(r) = \frac{r(r-1) + (b-r)(b-r-1)}{2}.$

Substituting $b = 2m+1$ and setting $r = x$, direct algebraic expansion yields

$f(x) = \frac{2x^2 - 2bx + b(b-1)}{2} = x^2 - bx + \frac{b(b-1)}{2}.$

Completing the square,

$f(x) = \left(x - \frac{b}{2}\right)^2 + \frac{b(b-2)}{4}.$

Since $b$ is odd, the integer values closest to $\frac{b}{2}$ are $\frac{b-1}{2}$ and $\frac{b+1}{2}$. Substituting $x = \frac{b-1}{2}$ gives

$f\left(\frac{b-1}{2}\right) = \binom{\frac{b-1}{2}}{2} + \binom{\frac{b+1}{2}}{2} = \frac{(b-1)^2}{4}.$

The same value is obtained for $x = \frac{b+1}{2}$. Since the quadratic form is convex in $x$, these points yield the global minimum over integers.

This establishes that for all integers $r$,

$f(r) \ge \frac{(b-1)^2}{4}.$

This certification fixes the key extremal structure of agreement within a single contestant.

Lemma 3

Let $f_i = f(r_i)$ denote the number of agreeing judge pairs contributed by contestant $i$. Summing over all contestants,

$\sum_{i=1}^a f_i = \sum_{\text{pairs of judges}} \text{number of contestants on which the pair agrees}.$

This identity holds because each pair of judges contributes $1$ to the count for every contestant on which they agree, and summing over all contestants counts exactly all such incidences.

This expresses the global agreement structure in two equivalent ways.

Main argument

For every contestant $i$, Lemma 2 gives

$f_i \ge \frac{(b-1)^2}{4}.$

Summing over all $a$ contestants,

$\sum_{i=1}^a f_i \ge a \cdot \frac{(b-1)^2}{4}.$

On the other hand, by the problem condition, each pair of judges agrees on at most $k$ contestants. Since there are $\binom{b}{2}$ pairs of judges,

$\sum_{i=1}^a f_i \le k \binom{b}{2} = k \cdot \frac{b(b-1)}{2}.$

Combining both inequalities,

$a \cdot \frac{(b-1)^2}{4} \le k \cdot \frac{b(b-1)}{2}.$

Dividing by $\frac{b(b-1)}{2}$ yields

$\frac{a(b-1)}{2b} \le k,$

which is equivalent to

$\frac{k}{a} \ge \frac{b-1}{2b}.$

This completes the proof. ∎

Verification of Key Steps

The first delicate point is the expression for $f(r)$. A direct recomputation confirms that every agreeing pair of judges is counted exactly once, since agreement forces both judges into either the pass set or the fail set, and these cases are disjoint.

The second delicate point is the minimization of $f(r)$. Writing $f(r)$ as a quadratic function in $r$ shows convexity, and checking the two nearest integers to $\frac{b}{2}$ confirms that these give the smallest value. Substituting $r = \frac{b\pm1}{2}$ reproduces $\frac{(b-1)^2}{4}$ exactly, confirming sharpness.

The third delicate point is the double counting identity. Reconstructing the sum from first principles shows that each triple consisting of a contestant and a pair of judges is counted once on both sides, ensuring no overcounting or undercounting occurs.

Alternative Approaches

An alternative approach replaces counting agreeing pairs with counting disagreements between judges. For each contestant, disagreement contributions are given by $r(b-r)$, and one can sum these over all contestants and relate them to the total number of disagreeing judge pairs. This leads to an equivalent inequality after optimizing the same quadratic structure.

Another viewpoint uses vector geometry by embedding each contestant as a point in ${0,1}^b$ and interpreting judge agreement as coordinate equality, then applying convexity of quadratic forms over the hypercube distribution of points. This perspective leads to the same extremal configuration where each contestant has nearly balanced numbers of passes and fails, corresponding to the minimum of $f(r)$.