IMO 1994 Problem 1

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 8m06s

Problem

Let $m$ and $n$ be two positive integers. Let $a_1$, $a_2$, $\ldots$, $a_m$ be $m$ different numbers from the set ${1, 2,\ldots, n}$ such that for any two indices $i$ and $j$ with $1\leq i \leq j \leq m$ and $a_i + a_j \leq n$, there exists an index $k$ such that $a_i + a_j = a_k$. Show that $$ \frac{a_1+a_2+...+a_m}{m} \ge \frac{n+1}{2} $$.

Exploration

Small cases suggest that whenever two selected elements are both “far from the top”, their sum, if it stays within ${1,\dots,n}$, must also be selected, which tends to force new larger elements into the set. For instance, with $n=5$, the admissible set ${2,4,5}$ satisfies the condition: $2+2=4$ is present, and all other admissible sums exceed $5$. Its average is already above $3=(5+1)/2$.

Attempts to force many small elements quickly generate forced larger elements through repeated addition, but the previous argument attempting to describe the set as a top interval fails because sparse configurations like ${2,4,5}$ are allowed.

A more stable structure emerges when elements are paired from opposite ends of the ordered list. This suggests comparing $a_i$ with $a_{m+1-i}$ rather than trying to describe the whole set directly.

Testing this idea on examples such as ${2,4,5}$ and ${3,4,5}$ shows that sums of “opposite pairs” tend to exceed $n$, hinting that the correct inequality is $a_i + a_{m+1-i} \ge n+1$.

No contradiction arises in small cases when this inequality holds, and it directly implies the desired average bound by summation.

Problem Understanding

A subset $A={a_1<\cdots<a_m}\subseteq {1,2,\dots,n}$ satisfies the property that whenever $a_i+a_j\le n$, the sum $a_i+a_j$ must also belong to $A$.

The goal is to prove

$$\frac{a_1+\cdots+a_m}{m} \ge \frac{n+1}{2},$$

equivalently

$$a_1+\cdots+a_m \ge \frac{m(n+1)}{2}.$$

The correct structural claim to establish is a symmetric lower bound:

$$a_i + a_{m+1-i} \ge n+1 \quad \text{for all } i.$$

Summation of these inequalities yields the result immediately.

Key Observations

If for some index $i$ one had $a_i + a_{m+1-i} \le n$, then the closure condition forces $a_i + a_{m+1-i}$ to be an element of $A$. This creates a new element strictly larger than $a_{m+1-i}$, since $a_i \ge 1$, and therefore produces an element that must lie among the largest part of the ordered set.

However, the position of $a_{m+1-i}$ already exhausts how many elements can lie above it, so inserting a strictly larger forced sum violates the fixed cardinality $m$. This contradiction prevents the inequality $a_i + a_{m+1-i} \le n$.

This pairing mechanism replaces any need for interval structure or extremal compression.

Solution

Let $A={a_1<a_2<\cdots<a_m}\subseteq {1,2,\dots,n}$ satisfy the given condition.

Lemma 1

For every $i$ with $1\le i\le m$, the inequality

$$a_i + a_{m+1-i} \ge n+1$$

holds.

Suppose the contrary for some index $i$, namely

$$a_i + a_{m+1-i} \le n.$$

Then by the problem condition, the number

$$s = a_i + a_{m+1-i}$$

belongs to $A$.

Since $a_i \ge 1$, it follows that

$$s = a_i + a_{m+1-i} > a_{m+1-i}.$$

Thus $s$ is strictly larger than $a_{m+1-i}$, so $s$ must lie among the elements

$${a_{m+1-i+1}, a_{m+2-i}, \dots, a_m},$$

which are exactly $i$ elements.

Now compare cardinalities in the interval $(a_{m+1-i}, n]$. The set already contains the $i$ elements

$$a_{m+1-i+1}, \dots, a_m,$$

all strictly greater than $a_{m+1-i}$, and it additionally contains $s$, which is also strictly greater than $a_{m+1-i}$. This gives at least $i+1$ distinct elements of $A$ exceeding $a_{m+1-i}$.

However, by definition of $a_{m+1-i}$ as the $(m+1-i)$-th smallest element, there are exactly $i$ elements of $A$ strictly greater than $a_{m+1-i}$. This contradiction shows that the assumption $a_i + a_{m+1-i} \le n$ is impossible.

Hence

$$a_i + a_{m+1-i} \ge n+1.$$

∎

Completion of the argument

Summing the inequalities over all $i$ from $1$ to $m$ yields

$$\sum_{i=1}^m \bigl(a_i + a_{m+1-i}\bigr) \ge m(n+1).$$

The left-hand side equals $2\sum_{i=1}^m a_i$, so

$$2\sum_{i=1}^m a_i \ge m(n+1).$$

Dividing by $2m$ gives

$$\frac{a_1+\cdots+a_m}{m} \ge \frac{n+1}{2}.$$

This completes the proof. ∎

Verification of Key Steps

The only delicate point is the contradiction in Lemma 1, which relies on counting elements strictly greater than $a_{m+1-i}$. The definition of order statistics ensures that exactly $i$ elements of the set lie above $a_{m+1-i}$, so any forced creation of an additional distinct element in that region contradicts the fixed size $m$.

The argument does not assume interval structure or maximality of missing elements, and it uses only the closure condition in the single forced-sum step.

Small cases such as $n=5$ with sets ${2,4,5}$, ${3,4,5}$, and ${2,3,5}$ confirm that whenever admissibility holds, opposite-pair sums exceed $n+1$, matching the proven inequality.

Alternative Approaches

An alternative method reformulates the condition as a restriction on additive triples in the ordered set and derives the same pairing inequality by induction on $m$, progressively inserting elements while preserving the lower bound on symmetric sums.