14th European Girls' Mathematical Olympiad (EGMO 2025)

Problem 2. An infinite increasing sequence a₁ < a₂ < a₃ < · · · of positive integers is called central if for every positive integer n, the arithmetic mean of the first an terms of the sequence is equal to a_n. Show that there exists an infinite sequence b₁, b₂, b₃, . . . of positive integers such that for every central sequence a₁, a₂, a₃, . . ., there are infinitely many positive integers n with a_n = b_n.

SOLUTION 1
Sequence is central if:
$\sum_{i=1}^{a_n} a_i = a_n ^2$ Let $x_i = a_i - i$ .
Becuase $a$ is strictly increasing, $x$ is nonnegative and increaseing.
By some algebraic manipulations we get:
$\sum_{i=1}^{x_n+n-1} (i-x_i) = x_{x_n+n}$ If for some $n$ $x_{n+1}=x_n$ by the sum above we get
$x_{x_n+n+1}=x_n+n$ We want to prove that this happens i.o.
If that's true there are infinitey many $k$ such that $x_k=k-1$ and by taking $b_i=2i-1$ we are done.
If this doesn't happen i.o. $x$ is eventually strictly increasing. Then sequance $i-x_i$ is decreasing.
It can't become negative because of term $i-x_i$ in sum. Because this sequance is bounded and monotone it is eventually constant.
Then eventually $x_i=i-d$ for some $d$ and by plugging this in original sum we get $d=1$ and again $b_i=2i-1$ works and we are done.

SOLUTION 2
We claim that $b_i=2i+1$ just works perfectly.
First notice having consecutive terms on $a_i$ would be lovely as if $a_i=\ell$ and $a_{i+1}=\ell+1$ then $a_{\ell+1}=(\ell+1)^2-\ell^2=2\ell+1$ which belongs on the sequence so if this happend infinitely many times we are done, else...
Suppose now for all $n \ge N$ we have that $a_{n+1}-a_n \ge 2$ then we have to explore how the growth of the sequence itself fights with the rest of components due to the increasingness we are given.
To do this just notice that if at any point for a term $k$ we had that $a_k \ge 2k$ then it also would follow that $a_n \ge 2n$ for all $n \ge \max(n,k)$ due to the assumption above but then pick some $a_j>1434k$ due to increasingness such that $j>1434k!$ too and pick a $j'$ with similar propeties such that $j'>j!$ (yes the excesive bounding here is not needed I just do it for the memes then $\sum_{i=a_j+1}^{a_j'} a_i=a_j'^2-a_j^2$ however we also have that $\sum_{i=a_j+1}^{a_j'} a_i>\sum_{i=a_j+1}^{a_j'} 2i-1=a_j'^2-a_j^2$ which is clearly a contradiction therefore it must never happen that $a_n \ge 2n$ and thus $a_n \le 2n-1$ for all positive integers $n$ and however this shows that $a_n^2=\sum_{i=1}^{a_n} a_i \le \sum_{i=1}^{a_n} 2i-1=a_n^2$ must force equality everywhere and thus in this case $a_n=2n-1$ for all positive integers $n$ and clearly $b_i$ would also contain infinitely many of these, thus either way we are done

SOLUTION 3
We claim that $a_n = 2n - 1$ holds infinitely many times for any central sequence. FTSOC suppose not for some sequence $a_n$ .

Define $d_{i} = a_{i} - a_{i-1}$ where $a_0 = 0$ .

Claim: $d_{i+1} \ne 1$ for sufficiently large $i$ .
Proof: If this wasn't the case, then
$a_{a_{i+1}} = a_{i+1}^2 - a_i^2 = 2a_{i+1} - 1$ holds infinitely many times, contradiction. $\blacksquare$

Claim: $d_1 + d_2 + \dots + d_n = 2n+1$ for sufficiently large $n$ .
Proof: Fix large $N = a_i$ . Note that
$a_1 + a_2 + \dots + a_N = \sum_{i=1}^N d_i \cdot (N+1 - i)$ Since $a_1 + a_2 + \dots + a_N = N^2$ , equality holds in the case where $d_i = 2$ . We can now rewrite this as
$\sum_{i=1}^N (d_i - 2) \cdot (N+1 - i) = -N$ Now let $\alpha_i$ be equal to the nonzero values of $d_i - 2$ . Then by the above $\alpha_i = -1$ finitely many times, say $k$ times. Define $A_i = \alpha_1 + \dots + \alpha_i$ . If $\alpha_i$ occurs at least $2k$ times, then we get that for large $N$ ,
$-N > \sum_{i=1}^{2k+1} \alpha_i \cdot (N+1 - i) = A_{2k+1} \cdot N + O(1)$ which is a contradiction since $A_{2k} \ge 0$ . This means that there must be finitely many $\alpha_i$ , say there are $t$ . Then we must have that
$-N = \sum_{i=1}^{t} \alpha_i \cdot (N+1 - i) = A_t \cdot N + O(1)$ for large $N$ , so $A_t = -1$ . Finally, we have that
$d_1 + d_2 + \dots + d_n = 2n + \alpha_1 + \dots + \alpha_t = 2n-1$ as desired.