IMO 2005 · Problem 6

In a mathematical competition, in which 6 problems were posed to the participants, every two of these problems were solved by more than \(\frac{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.

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

Solution

Let \(N\) be the number of contestants. For distinct problems \(i,j\), let \(a_{ij}=a_{ji}\) be the number of contestants who solved both, and put \[ m=\min_{i<j}a_{ij},\qquad T=\sum_{i<j}a_{ij}. \] The hypothesis gives \(5m>2N\). Since these quantities are integers, \[ 5m\ge 2N+1, \qquad\text{so}\qquad T\ge 15m\ge 6N+3. \tag{1} \]

A contestant who solved \(r\) problems contributes \(\binom r2\) to \(T\).

Suppose, for a contradiction, that at most one contestant solved exactly five problems. If there were none, every contestant would have solved at most four, giving \(T\le 6N\), contrary to (1). Thus there is exactly one such contestant, whom we call \(A\).

Every other contestant solved at most four problems. If any of them solved at most three, then \[ T\le \binom52+\binom32+(N-2)\binom42 =10+3+6(N-2)=6N+1, \] again contradicting (1). Consequently, every contestant other than \(A\) solved exactly four problems, and \[ T=10+6(N-1)=6N+4. \] Together with (1), this yields \[ 6N+3\le 15m\le 6N+4. \] As \(15m\) is divisible by \(3\), necessarily \(15m=6N+3\). Hence \[ \sum_{i<j}(a_{ij}-m)=T-15m=1. \] All summands are nonnegative integers. Therefore exactly one pair of problems has \(a_{ij}=m+1\), and all other pairs have \(a_{ij}=m\). Call this pair the exceptional pair.

For each problem \(i\), define \[ D_i=\sum_{j\ne i}a_{ij}. \] If \(A\) solved problem \(i\), then \(A\) contributes \(4\) to \(D_i\). Each other contestant who solved \(i\) contributes \(3\), because that contestant solved exactly four problems. Thus, for every problem \(i\) solved by \(A\), \[ D_i\equiv 1\pmod 3. \tag{2} \]

Since \(A\) solved five of the six problems, at least one problem \(u\) in the exceptional pair was solved by \(A\). There is also a problem \(v\) solved by \(A\) outside that pair. By the description of the pair counts, \[ D_u=5m+1,\qquad D_v=5m. \] Their difference is \(1\), contradicting (2), which says that their difference is divisible by \(3\).

Therefore at least two contestants solved exactly five problems each. \(\square\)

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