IMO 1994 · Problem 1

Let \(m\) and \(n\) be positive integers. Let \(a_1,a_2,\ldots,a_m\) be distinct elements of \(\{1,2,\ldots,n\}\) such that whenever \(a_i+a_j\le n\) for some \(i,j\), \(1\le i\le j\le m\), there exists \(k\), \(1\le k\le m\), with \(a_i+a_j=a_k\). Prove that \[ \frac{a_1+a_2+\cdots+a_m}{m}\ge\frac{n+1}{2}. \]

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

Solution

Put \(A=\{a_1,a_2,\ldots,a_m\}\) and let \(d=\min A\). The hypothesis implies that \[ x\in A,\qquad x+d\le n \quad\Longrightarrow\quad x+d\in A. \] This also holds when \(x=d\), since the hypothesis allows \(i=j\).

Partition \(A\) into its nonempty residue classes modulo \(d\). In any one class, let \(b\) be the smallest element and put \[ q=\left\lfloor\frac{n-b}{d}\right\rfloor. \] Repeatedly applying the implication above shows that this class consists exactly of \[ b,\ b+d,\ \ldots,\ b+qd. \] Indeed, all these numbers belong to \(A\), and they exhaust the integers between \(b\) and \(n\) congruent to \(b\) modulo \(d\).

Let \(c=b+qd\) be its last element. By the definition of \(q\), we have \(c+d>n\), so \[ c\ge n-d+1. \] Also \(b\ge d\), because \(d=\min A\). Consequently, the average of the elements in this class is \[ \frac{b+c}{2}\ge\frac{d+(n-d+1)}{2}=\frac{n+1}{2}. \] The same calculation applies to a class with only one element.

Thus every nonempty residue class has average at least \((n+1)/2\). Summing their sums gives \[ a_1+a_2+\cdots+a_m\ge m\frac{n+1}{2}, \] which proves the required inequality. \(\square\)

The solution was checked against John Scholes' IMO solution archive (Kalva).