IMO 1975 Problem 2
The statement concerns an arbitrary increasing sequence of positive integers.
Proposed by: -
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 35m15s
Problem
Let $a_1, a_2, a_3, \cdots$ be an infinite increasing sequence of positive integers. Prove that for every $p \geq 1$ there are infinitely many $a_m$ which can be written in the form $$ a_m = xa_p + ya_q $$ with $x, y$ positive integers and $q > p$.
Exploration
The statement concerns an arbitrary increasing sequence of positive integers. Nothing is assumed about density, divisibility, or additive structure, so the argument must use only order properties and infinitude.
The conclusion asks for infinitely many terms of the sequence that belong to the additive semigroup generated by two fixed terms $a_p$ and $a_q$, with positive coefficients. Since $q$ may depend on $p$, the first task is to choose a suitable $q$.
A natural idea is to examine the residues of the sequence modulo $a_p$. There are only finitely many residue classes modulo $a_p$, but infinitely many sequence elements beyond $a_p$. Hence at least one residue class contains infinitely many terms. If that residue class is represented by some later term $a_q$, then infinitely many $a_m$ satisfy
$$a_m \equiv a_q \pmod{a_p}.$$
For such $m$,
$$a_m = y a_q + k a_p$$
for some integer $k$, provided $y$ is chosen appropriately.
The difficulty is that the coefficients must both be positive. If one merely writes
$$a_m-a_q \equiv 0 \pmod{a_p},$$
then
$$a_m=a_q+k a_p,$$
and positivity requires $k>0$. This fails when $a_m=a_q$. Since only finitely many terms equal $a_q$, the infinitely many larger terms in the same residue class should give $k>0$ automatically.
One should test small examples.
Take $a_n=n$. Fix $p=2$, so $a_p=2$. Among all integers, infinitely many are odd. Choose $a_q=3$. Then every odd integer greater than $3$ equals
$$x\cdot 2 + 1\cdot 3.$$
This works.
Take $a_n=2^n$. Fix $p=2$, so $a_p=4$. Modulo $4$, every later term is congruent to $0$. Choose $q=3$, so $a_q=8$. Then every sufficiently large power of two satisfies
$$2^m = x\cdot 4 + 1\cdot 8.$$
Indeed,
$$2^m=8+(2^{m-2}-2)\cdot 4,$$
and the coefficient is positive for $m\ge 4$.
The core insight is therefore purely pigeonhole-theoretic: infinitely many sequence terms share one residue class modulo $a_p$, and choosing one representative $a_q$ from that class forces infinitely many later terms to differ from $a_q$ by a positive multiple of $a_p$.
The most dangerous hidden error is forgetting that the coefficient of $a_p$ must be positive, not merely nonnegative. One must explicitly exclude the finitely many terms not exceeding $a_q$.
Problem Understanding
We are given an arbitrary strictly increasing infinite sequence of positive integers
$$a_1<a_2<a_3<\cdots.$$
For each fixed index $p\ge1$, we must prove the existence of another index $q>p$ such that infinitely many terms of the sequence can be expressed as
$$a_m=x a_p+y a_q,$$
where $x,y$ are positive integers.
This is a Type B problem. The goal is to prove a universal statement.
The mathematical objects involved are residue classes modulo a fixed integer and additive representations using two sequence elements. The statement does not assert that every sufficiently large term has such a representation; it only asks for infinitely many representable terms.
The core difficulty is that the sequence may be extremely sparse and irregular. Arguments relying on density or arithmetic progression structure cannot work. The proof must exploit a property shared by all infinite sequences of integers, namely that finitely many residue classes cannot accommodate infinitely many integers without repetition.
A naive approach might try to choose $q=p+1$ and derive representations directly. This fails for arbitrary sequences. The correct strategy is to select $q$ according to residue classes modulo $a_p$.
Proof Architecture
The proof will use two lemmas.
Lemma 1 states that for any fixed modulus $a_p$, at least one residue class modulo $a_p$ contains infinitely many sequence terms. This follows from the pigeonhole principle because there are only $a_p$ residue classes.
Lemma 2 states that if infinitely many sequence terms are congruent to a fixed later term $a_q$ modulo $a_p$, then infinitely many terms admit a representation
$$a_m=x a_p+a_q$$
with $x$ a positive integer. This follows because congruence implies divisibility of the difference, and all sufficiently large terms in the class exceed $a_q$.
The hardest direction is ensuring positivity of the coefficient of $a_p$. Congruence alone yields only an integer multiple. The proof must explicitly use strict monotonicity of the sequence to guarantee positivity.
The step most likely to fail under scrutiny is the transition from congruence to a representation with positive coefficients. A careless argument might permit coefficient $0$.
Solution
Fix an arbitrary integer $p\ge1$. We shall prove that there exists an index $q>p$ such that infinitely many terms of the sequence admit a representation
$$a_m=x a_p+y a_q$$
with $x,y\in\mathbb{Z}_{>0}$.
Lemma 1
Among the residue classes modulo $a_p$, at least one contains infinitely many terms of the sequence.
Proof
The integers modulo $a_p$ form exactly $a_p$ residue classes:
$$0,1,\dots,a_p-1.$$
Every term $a_n$ belongs to one of these classes.
Assume that each residue class modulo $a_p$ contains only finitely many terms of the sequence. Since there are finitely many residue classes, the union of all these finite sets would also be finite. That would imply that the sequence contains only finitely many terms, contradicting the hypothesis that the sequence is infinite.
Hence at least one residue class modulo $a_p$ contains infinitely many terms of the sequence. ∎
This lemma establishes the existence of infinitely many sequence elements sharing one residue modulo $a_p$; without this infinite repetition, no additive structure could be forced.
Choose one residue class modulo $a_p$ that contains infinitely many terms. Since only finitely many indices satisfy $n\le p$, this residue class contains some term $a_q$ with
$$q>p.$$
Lemma 2
Infinitely many terms of the sequence can be written in the form
$$a_m=x a_p+a_q$$
with $x\in\mathbb{Z}_{>0}$.
Proof
Consider all terms $a_m$ lying in the same residue class modulo $a_p$ as $a_q$. By construction, there are infinitely many such terms.
For each such $m$,
$$a_m\equiv a_q \pmod{a_p}.$$
Hence
$$a_p\mid(a_m-a_q).$$
Therefore there exists an integer $x_m$ such that
$$a_m-a_q=x_m a_p.$$
Since the sequence is strictly increasing, the equality $a_m=a_q$ occurs only when $m=q$. All other terms in this residue class satisfy
$$a_m>a_q.$$
For those terms,
$$x_m=\frac{a_m-a_q}{a_p}>0.$$
Thus
$$a_m=x_m a_p+a_q.$$
There are infinitely many terms in the chosen residue class and only one of them equals $a_q$. Consequently infinitely many satisfy
$$a_m=x_m a_p+a_q$$
with $x_m>0$. ∎
This lemma converts congruence information into the required additive representation; the strict increase of the sequence is essential because it forces the coefficient of $a_p$ to be positive rather than merely nonnegative.
We now complete the proof. For the fixed index $p$, choose $q>p$ as above. Lemma 2 shows that infinitely many terms of the sequence satisfy
$$a_m=x a_p+a_q.$$
Since
$$a_q=1\cdot a_q,$$
this has the required form
$$a_m=x a_p+y a_q$$
with positive integers
$$x=x_m,\qquad y=1.$$
Since $p$ was arbitrary, the statement holds for every $p\ge1$.
This completes the proof.
∎
Verification of Key Steps
The first delicate step is the application of the pigeonhole principle. One must distinguish between infinitely many integers distributed among finitely many classes and infinitely many distinct classes. Here the modulus is fixed at $a_p$, so there are exactly $a_p$ residue classes. If each class contained only finitely many sequence terms, their union would contain finitely many terms. This contradicts infinitude of the sequence itself.
The second delicate step is proving positivity of the coefficient of $a_p$. From
$$a_m\equiv a_q\pmod{a_p},$$
one obtains only
$$a_m-a_q=k a_p$$
for some integer $k$. A careless proof might permit $k=0$. Since the sequence is strictly increasing, the equality $a_m=a_q$ occurs only at the single index $m=q$. Every other term in the same residue class satisfies
$$a_m>a_q,$$
hence
$$k=\frac{a_m-a_q}{a_p}>0.$$
The third delicate point is ensuring that infinitely many usable terms remain after excluding the single term $a_q$. Removing one element from an infinite set leaves an infinite set. Thus infinitely many terms still satisfy the desired representation.
Alternative Approaches
Another approach begins by considering the infinite set
$${a_n \bmod a_p : n>p}.$$
Since there are only finitely many residues modulo $a_p$, some residue $r$ occurs infinitely often. Choose $q>p$ such that
$$a_q\equiv r\pmod{a_p}.$$
Then infinitely many indices $m$ satisfy
$$a_m\equiv a_q\pmod{a_p},$$
so
$$a_m=a_q+t_m a_p.$$
Strict monotonicity again yields $t_m>0$ for all sufficiently large $m$.
This proof is essentially equivalent to the main argument but suppresses the explicit lemma structure. The lemma-based presentation is preferable because it isolates the two independent ideas: infinite repetition of residues and positivity of coefficients.