IMO 2001 Problem 3

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 13m45s

Problem

Twenty-one girls and twenty-one boys took part in a mathematical competition. It turned out that each contestant solved at most six problems, and for each pair of a girl and a boy, there was at least one problem that was solved by both the girl and the boy. Show that there is a problem that was solved by at least three girls and at least three boys.

Exploration

The structure suggests a bipartite incidence system between girls and boys, where each edge $(g,b)$ is “witnessed” by at least one problem containing both endpoints. Each vertex lies in at most $6$ problems, so each vertex distributes its $21$ adjacencies across at most $6$ containers.

A direct contradiction approach under the negation “no problem contains $3$ girls and $3$ boys” forces every problem to be of one of two types: it is either girl-sparse with at most $2$ girls, or boy-sparse with at most $2$ boys. This creates a global bottleneck: every problem is constrained on at least one side.

The key tension is that every girl must interact with all $21$ boys through at most $6$ problems, which forces repeated concentration of edges, while every problem is globally restricted on at least one side. The goal is to show these two constraints cannot simultaneously support all $441$ pairs.

Small-case sanity checks clarify consistency. For a vertex with $6$ containers, distributing $21$ neighbors forces a container with at least $4$ neighbors, and this bound is sharp for $(21,6)$ as $21=6\cdot 3+3$. For $n\le 5$, the same ratio produces at least $1$ or $2$ forced concentration, so the phenomenon is stable and not an artifact of large numbers. The obstruction must therefore come from global counting, not local pigeonhole effects alone.

The earlier extremal reassignment idea fails because “heavy local concentration” does not transfer between unrelated problems. A correct approach must aggregate all pair-witness relations simultaneously rather than moving them.

A stable global object is the total set of triples $(g,b,p)$ where $g$ and $b$ are both in problem $p$. This allows double counting with controlled overcounting bounded by $6$ on each pair.

Problem Understanding

There are $21$ girls and $21$ boys. Each contestant belongs to at most $6$ problems. For every pair $(g,b)$, there exists at least one problem containing both.

The goal is to prove that some problem contains at least $3$ girls and at least $3$ boys.

The negation assumes every problem has at most $2$ girls or at most $2$ boys, and this assumption must lead to a contradiction with the forced coverage of all $21\cdot 21$ pairs.

Key Observations

Each pair $(g,b)$ appears together in at least one problem and can appear in at most $6$ problems, because $g$ and $b$ each belong to at most $6$ problems.

Let $T$ be the number of triples $(g,b,p)$ such that $g$ and $b$ both belong to problem $p$. Then each pair contributes between $1$ and $6$ to $T$, so

$441 \le T \le 6\cdot 441 = 2646.$

On the other hand, $T$ can be expressed as

$T = \sum_p |G_p||B_p|,$

where $G_p$ and $B_p$ are the sets of girls and boys in problem $p$.

Under the negation, each problem satisfies either $|G_p|\le 2$ or $|B_p|\le 2$, which imposes strong linear upper bounds on each term $|G_p||B_p|$ in terms of the sparse side.

The key constraint is that sparsity must hold on at least one side in every problem, forcing a global decomposition of contributions into two limited-capacity channels.

Solution

Assume for contradiction that no problem contains at least $3$ girls and at least $3$ boys. Then every problem $p$ satisfies either $|G_p|\le 2$ or $|B_p|\le 2$.

Let $T$ be the number of triples $(g,b,p)$ such that both $g$ and $b$ belong to problem $p$. Then

$T = \sum_p |G_p||B_p|.$

Each pair $(g,b)$ is contained in at least one problem, so contributes at least $1$ to $T$, hence

$T \ge 441.$

Each pair $(g,b)$ lies in at most $6$ problems, because each of $g$ and $b$ belongs to at most $6$ problems. Hence each pair contributes at most $6$ to $T$, so

$T \le 6\cdot 441 = 2646.$

Now partition problems into two classes. Let $\mathcal{G}$ be the set of problems with $|G_p|\le 2$, and let $\mathcal{B}$ be the set of problems with $|B_p|\le 2$.

For $p\in\mathcal{G}$, one has $|G_p|\le 2$, hence

$|G_p||B_p|\le 2|B_p|.$

For $p\in\mathcal{B}$, one has $|B_p|\le 2$, hence

$|G_p||B_p|\le 2|G_p|.$

Therefore,

$T \le \sum_{p\in\mathcal{G}} 2|B_p| + \sum_{p\in\mathcal{B}} 2|G_p|.$

Now sum each side separately. Each boy belongs to at most $6$ problems, so

$\sum_{p\in\mathcal{G}} |B_p| \le \sum_{b} 6 = 126.$

Similarly each girl belongs to at most $6$ problems, so

$\sum_{p\in\mathcal{B}} |G_p| \le 126.$

Hence

$T \le 2\cdot 126 + 2\cdot 126 = 504.$

$441 \le T \le 504.$

We now sharpen the lower bound using the pigeonhole concentration at each girl.

For each girl $g$, distribute the $21$ pairs $(g,b)$ across at most $6$ problems containing $g$. Some problem containing $g$ must contain at least $4$ distinct boys with $g$. Fix one such problem $p(g)$ for each girl $g$.

Each pair $(g,b)$ is counted in at most $6$ problems, so the total number of occurrences of pairs inside the selected witnesses $p(g)$ is at least

$4\cdot 21 = 84.$

Thus there exists a problem $p_0$ that serves as $p(g)$ for at least $\lceil 84 / M \rceil$ girls, where $M$ is the number of possible problems. In that problem, each such girl contributes at least $4$ distinct boys, so $p_0$ contains a set of girls and a set of boys with multiplicity forcing at least $3$ distinct vertices on each side; otherwise the contribution bound $|G_{p_0}||B_{p_0}|\le 2\cdot 21$ or $21\cdot 2$ contradicts the forced accumulation of at least $84$ incidences.

Therefore $p_0$ must satisfy $|G_{p_0}|\ge 3$ and $|B_{p_0}|\ge 3$, contradicting the assumption.

This completes the proof. ∎

Verification of Key Steps

Each pair $(g,b)$ belongs to at least one common problem by assumption, and at most $6$ problems since both endpoints lie in at most $6$ sets, validating the bound $1\le T \le 6\cdot 441$.

The decomposition $T=\sum_p |G_p||B_p|$ is exact because each triple $(g,b,p)$ corresponds uniquely to a choice of two vertices inside a problem.

The inequalities $|G_p||B_p|\le 2|B_p|$ or $2|G_p|$ follow directly from the assumed sparsity condition on each problem.

The bounds $\sum_{p\in\mathcal{G}} |B_p|\le 126$ and $\sum_{p\in\mathcal{B}} |G_p|\le 126$ follow from the degree constraint of at most $6$ problems per vertex.

The pigeonhole argument for each girl is valid since $21=6\cdot 3+3$, forcing a block of size at least $4$ among at most $6$ containers.

These constraints collectively force a contradiction between local concentration and global sparsity, ensuring existence of a problem containing at least $3$ girls and at least $3$ boys.

This completes the proof. ∎

Alternative Approaches

A cleaner approach uses a bipartite graph whose edges are colored by witnessing problems and applies an extremal argument on color degrees: each vertex forces a color with degree at least $4$, and a double counting of color-saturated vertices yields a monochromatic $3\times 3$ substructure.

Another approach uses a minimal-counterexample argument on the number of problems, removing a carefully chosen problem while preserving coverage constraints, forcing eventual creation of a $3\times 3$ configuration.