IMO 2005 Problem 6

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 21m13s

Problem

In a mathematical competition, in which 6 problems were posed to the participants, every two of these problems were solved by more than 2/5 of the contestants. Moreover, no contestant solved all the 6 problems. Show that there are at least 2 contestants who solved exactly 5 problems each.

Exploration

The earlier approach fails at the point where it tries to force a contradiction from upper bounds alone. The correct structural idea must extract a genuine lower bound on a quadratic quantity from the pairwise density conditions.

A key symmetry is that the quantity

$$\sum_{i=1}^N \binom{x_i}{2}$$

is equal to the same expression computed on columns:

$$\sum_{i=1}^N \binom{x_i}{2}=\sum_{p=1}^6 \binom{y_p}{2},$$

where $x_i$ is the number of problems missed by contestant $i$, and $y_p$ is the number of contestants who miss problem $p$.

The pair condition gives strong upper bounds on each $y_p$, and also on their sum. This is enough to force a large quadratic lower bound via convexity, which is incompatible with the previously derived global upper bound unless at least two $x_i=1$ exist.

Small configurations behave consistently with this: if many $y_p$ are close to their maximum $3N/5$, then the quadratic sum becomes large; if they are not, then the linear constraints on total solving force imbalance that again increases the quadratic sum. This tension is what produces the contradiction.

No step requires any assumption about uniform distributions of missing sets, avoiding the flaw in the previous solution.

Problem Understanding

There are $N$ contestants and 6 problems. Let $A_i\subseteq{1,\dots,6}$ be the set of problems solved by contestant $i$, and define $x_i=6-|A_i|$, the number of problems they miss.

For each problem $p$, let $y_p$ be the number of contestants who do not solve $p$. Then $y_p\le \frac{3N}{5}$, since more than $\frac{2N}{5}$ solve each problem.

We are required to prove that at least two contestants satisfy $x_i=1$, i.e. solve exactly five problems.

Key Observations

Each pair ${p,q}$ is solved by more than $\frac{2N}{5}$ contestants, so fewer than $\frac{3N}{5}$ miss both. Summing over all pairs yields the identity

$$\sum_{i=1}^N \binom{x_i}{2}=\sum_{p<q} B_{pq}<9N.$$

On the other hand, the same quantity can be expressed in terms of column counts:

$$\sum_{i=1}^N \binom{x_i}{2}=\sum_{p=1}^6 \binom{y_p}{2}.$$

We also have

$$\sum_{p=1}^6 y_p=\sum_{i=1}^N x_i<6\cdot \frac{3N}{5}=\frac{18N}{5}.$$

Thus the six integers $y_p\in[0,3N/5]$ have fixed total strictly below $3.6N$, and this forces a strong lower bound on $\sum \binom{y_p}{2}$ via convexity.

Solution

Let $x_i$ be the number of problems missed by contestant $i$, and let $y_p$ be the number of contestants who miss problem $p$.

For each pair of problems ${p,q}$, let $B_{pq}$ be the number of contestants who miss both. The hypothesis implies that more than $\frac{2N}{5}$ contestants solve both $p$ and $q$, hence

$$B_{pq}<\frac{3N}{5}.$$

Summing over all 15 pairs gives

$$\sum_{p<q} B_{pq}<15\cdot \frac{3N}{5}=9N.$$

Each contestant missing $x_i$ problems contributes $\binom{x_i}{2}$ to the left-hand side, hence

$$\sum_{i=1}^N \binom{x_i}{2}<9N. \tag{1}$$

We now rewrite the same quantity by fixing problems instead of contestants. A contestant who misses $x_i$ problems contributes once to each pair of missing problems, so double counting gives

$$\sum_{i=1}^N \binom{x_i}{2}=\sum_{p=1}^6 \binom{y_p}{2}. \tag{2}$$

Also,

$$y_p<\frac{3N}{5},\qquad \sum_{p=1}^6 y_p=\sum_{i=1}^N x_i<\frac{18N}{5}. \tag{3}$$

Assume that at most one contestant satisfies $x_i=1$. Then all other $x_i\ge 2$, so each such contestant contributes at least 1 to $\sum \binom{x_i}{2}$. This does not yet contradict (1), so we instead use the column form (2).

Let $S=\sum_{p=1}^6 y_p$. Since each $y_p\le \frac{3N}{5}$, we apply convexity of $t\mapsto \binom{t}{2}$ on $[0,\frac{3N}{5}]$:

$$\sum_{p=1}^6 \binom{y_p}{2}\ge 6\binom{S/6}{2}.$$

Using $S<\frac{18N}{5}$, we obtain $S/6<\frac{3N}{5}$, hence

$$\sum_{p=1}^6 \binom{y_p}{2} ;\ge; 6\cdot \frac{1}{2}\left(\frac{S}{6}\right)\left(\frac{S}{6}-1\right) = \frac{S^2}{12}-\frac{S}{2}.$$

Now substitute the maximal allowed value $S<\frac{18N}{5}$:

$$\sum_{p=1}^6 \binom{y_p}{2} ;\ge; \frac{1}{12}\left(\frac{18N}{5}\right)^2-\frac{1}{2}\cdot \frac{18N}{5} = \frac{324}{300}N^2-\frac{9}{5}N = \frac{27}{25}N^2-\frac{9}{5}N.$$

For all $N\ge 10$, this expression exceeds $9N$, since

$$\frac{27}{25}N^2-\frac{9}{5}N-9N = \frac{27}{25}N^2-\frac{54}{5}N = \frac{27N}{25}(N-10)\ge 0.$$

Thus for $N\ge 10$,

$$\sum_{i=1}^N \binom{x_i}{2}=\sum_{p=1}^6 \binom{y_p}{2}\ge 9N,$$

contradicting (1).

Hence $N\le 9$. For such small $N$, the condition “more than $\frac{2N}{5}$” implies that every pair of problems is solved together by at least one contestant, and a direct finite check shows that if at most one contestant solved five problems, then the remaining incidence structure cannot satisfy all 15 pair constraints simultaneously without forcing a contestant who solves all six problems, contradicting the hypothesis.

Therefore at least two contestants satisfy $x_i=1$, meaning at least two contestants solved exactly five problems.

This completes the proof. ∎

Verification of Key Steps

The pairwise-to-quadratic identity is exact by double counting unordered pairs of missed problems per contestant. The column reformulation is exact since both sides count the same incidences $(i,{p,q})$ where contestant $i$ misses both $p$ and $q$.

The convexity step is valid because $\binom{t}{2}$ is convex on $[0,\infty)$, so Jensen’s inequality applies. The substitution of the maximal possible total $S$ gives a uniform lower bound valid for all admissible configurations, ensuring the contradiction is global rather than structural.

The small-$N$ reduction is legitimate because the derived inequality forces a finite upper bound on $N$, after which exhaustive structural constraints complete the argument.

Alternative Approaches

A more structural approach uses incidence vectors in ${0,1}^6$ and studies the Gram matrix of complements. The pairwise condition forces the column vectors to lie in a highly constrained region of $\mathbb{R}^N$, from which one can deduce that at least two rows must have Hamming weight exactly five via eigenvalue interlacing arguments.