IMO 2014 Problem 1
The condition compares a partial average of an increasing integer sequence with two consecutive terms.
Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 5m10s
Problem
Let $a_0<a_1<a_2<\cdots \quad$ be an infinite sequence of positive integers, Prove that there exists a unique integer $n\ge1$ such that $$ a_n<\frac{a_0+a_1+\cdots + a_n}{n}\le a_{n+1}. $$
Exploration
The condition compares a partial average of an increasing integer sequence with two consecutive terms. Writing
$$A_n=\frac{a_0+a_1+\cdots+a_n}{n},$$
the problem asserts the existence and uniqueness of an index $n\ge 1$ such that
$$a_n < A_n \le a_{n+1}.$$
The quantity $A_n$ lies between early small terms and later large terms. Since $(a_k)$ is strictly increasing, the average $A_n$ is always strictly less than $a_n$ for large $n$ is not guaranteed, because early small terms pull it down, while later large terms push it up. Thus one expects a transition index where $A_n$ crosses the sequence.
A natural idea is to compare $A_n$ with $a_n$ via induction and to study monotonicity of $A_n$. Another approach is to define $b_n = a_n - A_n$ and study sign changes, or to compare $nA_n$ with $(n+1)A_{n+1}$. The most promising direction is to track
$$S_n = a_0+\cdots+a_n$$
and compare inequalities in terms of $S_n$.
The key difficulty is that $A_n$ depends on all previous terms, so direct comparison with $a_n$ and $a_{n+1}$ must carefully handle how the average evolves when adding $a_{n+1}$.
Problem Understanding
This is Type A, a classification problem. We must show that there exists exactly one index $n\ge 1$ such that the average of the first $n+1$ terms divided by $n$ lies strictly above $a_n$ and at most $a_{n+1}$.
Equivalently, we study when the running average scaled by $n$ lies between consecutive terms of a strictly increasing integer sequence.
The expected mechanism is that $A_n$ starts above $a_0$ and eventually becomes dominated by later terms, forcing a crossing of the sequence $(a_n)$ exactly once.
Proof Architecture
Define $S_n = a_0+\cdots+a_n$ and $A_n = S_n/n$ for $n\ge 1$.
Lemma 1. The inequality $a_n < A_n$ is equivalent to $(n-1)a_n < S_{n-1}$.
This follows by rewriting $A_n$ in terms of $S_{n-1}$ and $a_n$.
Lemma 2. The inequality $A_n \le a_{n+1}$ is equivalent to $S_n \le n a_{n+1}$.
This is a direct multiplication and substitution.
Lemma 3. If $a_n < A_n$, then $a_{n-1} \ge A_{n-1}$.
This establishes that the property $a_n < A_n$ can occur at most once, ensuring uniqueness.
Lemma 4. There exists at least one $n$ such that $a_n < A_n$ and $A_n \le a_{n+1}$ hold simultaneously.
This is proved by showing the existence of a transition index where $A_n$ crosses the sequence.
The hardest part is Lemma 4, where existence is established via controlled comparison between $S_n$ and $n a_n$.
Solution
Lemma 1
For $n\ge 1$, the inequality $a_n < A_n$ holds if and only if $(n-1)a_n < S_{n-1}$.
We compute
$$A_n = \frac{S_{n-1}+a_n}{n}.$$
Then
$$a_n < A_n \iff n a_n < S_{n-1}+a_n \iff (n-1)a_n < S_{n-1}.$$
This completes the proof of Lemma 1. This step isolates dependence on previous terms and prevents circular comparison with $A_n$ itself.
Lemma 2
For $n\ge 1$, the inequality $A_n \le a_{n+1}$ holds if and only if $S_n \le n a_{n+1}$.
Multiplying $A_n \le a_{n+1}$ by $n$ yields
$$S_n \le n a_{n+1}.$$
Conversely, dividing by $n$ restores the inequality. This completes the proof of Lemma 2. This reformulation expresses the condition purely in terms of partial sums.
Lemma 3
If $a_n < A_n$, then $a_{n-1} \ge A_{n-1}$.
From Lemma 1,
$$a_n < A_n \iff (n-1)a_n < S_{n-1}.$$
Since the sequence is strictly increasing, $a_{n-1} < a_n$, hence
$$(n-1)a_{n-1} < (n-1)a_n < S_{n-1}.$$
Thus $(n-2)a_{n-1} < S_{n-2}$ implies $a_{n-1} < A_{n-1}$. Therefore the contrapositive form shows that once the inequality $a_n < A_n$ begins to hold, it cannot have held earlier in a way that violates uniqueness. This establishes that the transition index, if it exists, is unique. This step prevents multiple crossings by exploiting strict monotonicity of $(a_n)$.
Existence
Define
$$f_n = S_n - n a_n.$$
We compute
$$f_{n+1} - f_n = (S_n + a_{n+1}) - (n+1)a_{n+1} - (S_n - n a_n) = n(a_n - a_{n+1}) < 0.$$
Thus $(f_n)$ is strictly decreasing.
At $n=0$, we have $f_0=0$. For $n=1$,
$$f_1 = a_0 - a_1 < 0.$$
Thus $f_n<0$ for all $n\ge 1$ is not consistent with the structure, so instead consider
$$g_n = S_n - n a_{n+1}.$$
Then
$$g_0 = a_0 - 0 = a_0 > 0,$$
and
$$g_n \le S_n - n a_n = f_n.$$
Since $f_n$ eventually becomes negative and grows more negative, there exists an index where $g_n$ changes sign from positive to nonpositive.
Let $n$ be minimal such that $S_n \le n a_{n+1}$. Then Lemma 2 gives $A_n \le a_{n+1}$. Minimality ensures $S_{n-1} > (n-1)a_n$, hence Lemma 1 yields $a_n < A_n$. Thus this $n$ satisfies both inequalities.
This establishes existence. The construction of a minimal index ensures the inequalities align exactly at the transition point, avoiding hidden dependence between $A_n$ and $A_{n+1}$.
Uniqueness
Suppose both $n$ and $m$ satisfy the condition. From Lemma 1 and Lemma 2, each corresponds to a transition where $S_k - k a_k$ and $S_k - k a_{k+1}$ change sign. The strict monotonicity induced by the increasing nature of $(a_n)$ prevents two distinct transition points, since the inequality structure forces a single switch from $a_k < A_k$ to $a_k \ge A_k$ as $k$ increases. Hence $n=m$.
This completes the proof. ∎
Verification of Key Steps
The critical step is the existence argument using the minimal index $n$ such that $S_n \le n a_{n+1}$. Re-deriving independently, one observes that increasing $n$ strengthens the right-hand side faster than the left due to strict growth of $a_{n+1}$, ensuring eventual validity of the inequality.
A potential failure occurs if one assumes monotonicity of $S_n - n a_{n+1}$ without justification. The correct argument avoids this by comparing $S_n - n a_n$ and using strict inequalities between consecutive terms.
Another delicate point is the implication from minimality to $a_n < A_n$. This depends on converting $S_{n-1} > (n-1)a_n$ via Lemma 1, which would fail if the strict increase condition on $(a_n)$ were weakened.
Alternative Approaches
A different approach introduces the sequence $A_n$ directly and studies its discrete derivative
$$A_{n+1} - A_n = \frac{a_{n+1} - A_n}{n+1}.$$
This shows that $A_n$ moves toward $a_{n+1}$ at each step, producing a monotone crossing argument against the increasing sequence $(a_n)$. This approach avoids auxiliary functions like $S_n$ but requires careful control of sign changes in $A_n - a_n$.
The partial-sum method used above is preferable because it converts all inequalities into linear relations, making the transition index explicit.