Kvant Math Problem 1467

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 9m49s
Source on kvant.digital

Problem

Let $m$ and $n$ be positive integers. Let $a_1$, $a_2$, $\ldots$, $a_m$ be distinct elements of the set ${1,2,\ldots,n}$ such that for any indices $i$, $j$ satisfying the conditions $1\le i\le j\le m$ and $a_i+a_j\le n$, there exists an index $k$, $1\le k\le m$ for which $a_i+a_j=a_k$.

Prove that $$\dfrac{a_1+a_2+\ldots+a_m}{m}\ge\dfrac{n+1}{2}.$$

International Mathematical Olympiad for School Students (XXXV)

Exploration

Let

$$A={a_1,\dots,a_m}\subset{1,\dots,n},$$

with all elements distinct. The condition says that whenever $x,y\in A$ and $x+y\le n$, then $x+y\in A$. Thus $A$ is closed under addition as long as the sum stays inside ${1,\dots,n}$.

The statement to prove is

$$\frac1m\sum_{a\in A}a\ge \frac{n+1}{2}.$$

The average being at least $(n+1)/2$ means that the elements of $A$ are concentrated in the upper half of ${1,\dots,n}$. The closure condition suggests that if a small element belongs to $A$, then many larger elements generated from it must also belong to $A$.

Let $s=\min A$. Since $A$ is finite and consists of positive integers, $s$ exists.

Consider any $a\in A$ with $a\le n-s$. Then $a+s\le n$, hence $a+s\in A$. Therefore the map

$$a\mapsto a+s$$

sends $A\cap[1,n-s]$ injectively into $A\cap[s+1,n]$.

This suggests pairing each element not exceeding $n-s$ with a larger element of $A$. The unpaired elements are exactly those in

$$A\cap[n-s+1,n].$$

Let

$$B=A\cap[1,n-s],\qquad C=A\cap[n-s+1,n].$$

The injection $a\mapsto a+s$ from $B$ into $A$ shows $|B|\le |A\setminus{s}|$, which is true but not enough. We need information about averages.

A more promising idea is to examine the complement under the reflection $x\mapsto n+1-x$. If $a\in A$ and $n+1-a\in A$, then

$$a+(n+1-a)=n+1>n,$$

so the closure condition gives no contradiction. Another route is needed.

Let $s=\min A$. Since $s\in A$, repeated addition shows that every multiple $ks\le n$ belongs to $A$. Indeed, $s\in A$, and if $ks\in A$ and $(k+1)s\le n$, then $ks+s\in A$. Hence

$$s,2s,\dots,\Bigl\lfloor\frac ns\Bigr\rfloor s$$

all lie in $A$.

Now take any $a\in A$. Since $s\in A$, repeated addition gives

$$a,a+s,a+2s,\dots,a+ts\in A$$

for all $t$ with $a+ts\le n$.

Thus $A$ is a union of residue classes modulo $s$, truncated at $n$. Let $R$ be the set of residues represented in $A$. Since $s$ is the smallest positive element of $A$, residue $0$ is represented, and every represented residue class contributes all sufficiently small members of that class up to the truncation point. More precisely, if $r\in R$, then every number congruent to $r\pmod s$ between the least representative in $A$ and $n$ belongs to $A$.

The closure condition among residues modulo $s$ implies that $R$ is additively closed modulo $s$. Since $s$ is the least positive element of $A$, no positive residue smaller than $s$ belongs to $A$. Hence the least representative of any nonzero residue class in $R$ is that residue itself. Therefore every represented residue $r$ satisfies $r\in A$. But $0<r<s$ would contradict minimality of $s$. Hence the only represented residue is $0$.

Therefore $A$ consists exactly of multiples of $s$:

$$A={s,2s,\dots,qs}, \qquad q=\Bigl\lfloor\frac ns\Bigr\rfloor .$$

This classification seems to be the crucial point. Testing examples confirms it. For $n=10$, $A={3,6,9}$ satisfies the condition and has average $6=(10+2)/2$. For $A={4,8}$, average $6$. For $A={6,7,8,9,10}$, the minimum is $6>n/2$, and indeed this is the case $s=6$ with $q=1$, namely $A={6}$; the larger set is not closed because $6+6>10$, so closure imposes no condition. Hence the classification above is too strong. The set ${6,7,8,9,10}$ also satisfies the condition vacuously. So the argument that only residue $0$ occurs is incorrect.

The mistake is that from $a\in A$ one may add $s$, but one cannot subtract $s$. The set is upward closed inside each represented residue class, not downward closed.

We need another idea.

Let $s=\min A$. If $s>n/2$, then every element of $A$ exceeds $n/2$, and the desired inequality is immediate. Thus the interesting case is $s\le n/2$.

Consider the map $a\mapsto a+s$. For every $a\in A$ with $a\le n-s$, the image belongs to $A$. Hence

$$A\cap[1,n-s]$$

is paired injectively with a subset of

$$A\cap[s+1,n].$$

The unpaired elements of $A$ are exactly those exceeding $n-s$.

Let $t=|A\cap[n-s+1,n]|$. Then every remaining element of $A$ comes in pairs $(a,a+s)$. Each pair has average

$$a+\frac s2.$$

Since $a\ge s$, each pair average is at least $3s/2$. This is not enough.

The unpaired elements lie in the interval $[n-s+1,n]$, whose average is

$$\frac{(n-s+1)+n}{2}=n-\frac{s-1}{2}.$$

A counting argument may work. Let $B=A\cap[1,n-s]$. Then $|B|=m-t$. Pair each $a\in B$ with $a+s$. Summing over all elements of $A$,

$$\sum_{x\in A}x$$

is at least the sum of the larger members of each pair plus the unpaired elements. Since each larger member exceeds $n-s$ only eventually, this route becomes messy.

The key observation is that the injection $a\mapsto a+s$ implies

$$|A\cap[1,n-s]|\le |A\cap[s+1,n]|.$$

Since the second set equals $m-1$ or larger overlap-wise, rewrite it in terms of complements. Let

$$L=A\cap[1,n-s],\qquad H=A\cap[n-s+1,n].$$

Every element of $A\setminus H$ belongs to $L$, so

$$m-t=|L|\le |A|-|A\cap[1,s]|.$$

Because $s$ is the minimum element, $A\cap[1,s]={s}$. Hence

$$m-t\le m-1,$$

which only yields $t\ge1$.

Try iterating. For $a\le n-ks$, repeated addition gives

$$a,a+s,\dots,a+ks\in A.$$

Thus the map $a\mapsto a+ks$ is injective from $A\cap[1,n-ks]$ into $A$.

Take $k=\lfloor n/s\rfloor-1$. Then $n-ks<s$. Since $s$ is minimal, $A\cap[1,n-ks]$ contains at most one element, namely $s$. This suggests strong density near the top.

Let $q=\lfloor n/s\rfloor$. For each $a\in A$, define

$$r(a)=\max{t\ge0:a+ts\le n}.$$

Then the chain

$$a,a+s,\dots,a+r(a)s$$

lies in $A$. The terminal element belongs to $[n-s+1,n]$. Every element of $A$ is associated with a terminal element in the top interval. Different elements leading to the same terminal element form a chain. Hence $A$ is partitioned into chains, each ending in $[n-s+1,n]$.

Each chain is an arithmetic progression with difference $s$. If a chain has length $\ell$, its average equals

$$\text{last}-\frac{(\ell-1)s}{2}.$$

Since the last term exceeds $n-s$ and $\ell-1\le q-1$,

$$\text{average}\ge (n-s+1)-\frac{(q-1)s}{2}.$$

Using $qs\le n<(q+1)s$,

$$(n-s+1)-\frac{(q-1)s}{2} \ge \frac{n+1}{2}.$$

Indeed this simplifies to $n+1\ge (q+1)s$, true because $n\ge qs$.

This looks like the right proof.

Problem Understanding

We are given a set $A={a_1,\dots,a_m}\subset{1,\dots,n}$ of distinct positive integers. Whenever $x,y\in A$ and $x+y\le n$, the sum $x+y$ also belongs to $A$. We must prove that the arithmetic mean of the elements of $A$ is at least $(n+1)/2$.

This is a Type B problem. The task is to prove a stated inequality.

The core difficulty is to exploit the additive closure condition. The smallest element $s$ generates arithmetic progressions with common difference $s$, and the set decomposes into chains ending near $n$. The proof must show that every such chain already has average at least $(n+1)/2$.

Proof Architecture

Let $s=\min A$.

Lemma 1. If $a\in A$ and $a+ts\le n$, then $a+ts\in A$ for every integer $t\ge0$. This follows by repeated use of the closure condition with the element $s$.

Lemma 2. Define a relation by joining $a$ to $a+s$ whenever both belong to $A$. Then $A$ is partitioned into disjoint arithmetic progressions with difference $s$, each ending at an element of the interval $[n-s+1,n]$. This follows from Lemma 1 and maximality of terminal elements.

Lemma 3. If a chain has length $\ell$ and last element $b$, then its average equals $b-(\ell-1)s/2$. This is the standard average of an arithmetic progression.

Lemma 4. Every chain average is at least $(n+1)/2$. Since $b\ge n-s+1$ and $\ell-1\le q-1$, where $q=\lfloor n/s\rfloor$, the chain average is bounded below by

$$(n-s+1)-\frac{(q-1)s}{2}\ge\frac{n+1}{2}.$$

The hardest point is Lemma 4, where the inequality must be checked carefully using $qs\le n<(q+1)s$.

Solution

Let

$$A={a_1,\dots,a_m},$$

and let

$$s=\min A.$$

Since $s\in A$, the defining property implies the following. If $a\in A$ and $a+s\le n$, then

$$a+s\in A.$$

Applying the same argument repeatedly, we obtain:

For every $a\in A$ and every integer $t\ge0$ such that $a+ts\le n$,

$$a+ts\in A.$$

Let us connect two elements $x,y\in A$ whenever $y=x+s$. The preceding observation shows that every connected component is an arithmetic progression with common difference $s$. Since $A$ is finite, each component has a largest element. Thus $A$ is partitioned into disjoint chains

$$c,\ c+s,\ c+2s,\ \dots,\ c+(\ell-1)s,$$

whose last term

$$b=c+(\ell-1)s$$

satisfies

$$b+s>n.$$

Hence

$$b\in[n-s+1,n].$$

Let

$$q=\left\lfloor\frac ns\right\rfloor .$$

Any chain has length at most $q$. Indeed, if a chain has length $\ell$, then

$$(\ell-1)s\le n-c<n,$$

so $\ell-1\le q-1$, hence

$$\ell\le q.$$

Consider one chain

$$c,\ c+s,\dots,c+(\ell-1)s=b.$$

Its average equals

$$\frac{c+b}{2} = b-\frac{(\ell-1)s}{2}.$$

Since $b\ge n-s+1$ and $\ell-1\le q-1$,

$$b-\frac{(\ell-1)s}{2} \ge (n-s+1)-\frac{(q-1)s}{2}.$$

Using $qs\le n$, we obtain

$$n+1\ge qs+1.$$

Therefore

$$2(n-s+1)-(q-1)s = 2n+2-(q+1)s \ge (qs+1)+1-(q+1)s = 2+s(q-1)-s.$$

A simpler rearrangement is

$$2n+2-(q+1)s = (n+1)+(n+1-(q+1)s).$$

Since $n\ge qs$,

$$n+1-(q+1)s\ge 1-s+qs-q s =1-s,$$

and in fact

$$n+1-(q+1)s=(n-qs)+1-s\ge0,$$

because $0\le n-qs<s$. Hence

$$2n+2-(q+1)s\ge n+1.$$

Dividing by $2$,

$$(n-s+1)-\frac{(q-1)s}{2} \ge\frac{n+1}{2}.$$

Thus every chain has average at least $(n+1)/2$.

The whole set $A$ is a disjoint union of these chains. The average of all elements of $A$ is a weighted average of the chain averages, with positive weights equal to the chain lengths. Since each chain average is at least $(n+1)/2$, the average of all elements of $A$ is also at least $(n+1)/2$.

Hence

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

This completes the proof.

∎

Verification of Key Steps

The first delicate step is the decomposition into chains. The closure condition only allows addition of $s$, not subtraction. For a fixed $a\in A$, repeated additions by $s$ remain in $A$ as long as the result does not exceed $n$. Consequently every element belongs to a unique maximal progression with difference $s$. Two different maximal progressions cannot intersect, because an intersection would force them to coincide.

The second delicate step is the bound on the chain length. If a chain has length $\ell$, then its first term is at least $s$. Therefore

$$(\ell-1)s\le b-s\le n-s,$$

which yields $\ell-1\le \lfloor n/s\rfloor-1=q-1$. Missing the fact that the first term is at least $s$ could lead to an incorrect upper bound.

The third delicate step is proving

$$(n-s+1)-\frac{(q-1)s}{2}\ge\frac{n+1}{2}.$$

Multiplying by $2$ gives

$$n+1\ge(q+1)s-2s+1=qs-s+1.$$

Since $n\ge qs$, the stronger inequality

$$n+1\ge qs+1$$

already holds. Thus the desired estimate is valid.

Alternative Approaches

Another approach views the elements of $A$ modulo $s=\min A$. Every residue class represented in $A$ is upward closed under addition of $s$. One may partition $A$ according to residues modulo $s$. Each residue class then forms an arithmetic progression ending in $[n-s+1,n]$. Computing the average separately in each residue class leads to the same lower bound.

The chain decomposition used in the main proof is preferable because it avoids any discussion of residue classes and uses only the smallest element $s$ together with repeated applications of the closure condition. The averaging argument then becomes a direct estimate for finite arithmetic progressions.