The old one is gone.

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

The old one is gone.

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: EGMO 2025 P2

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

66 posts

#1 h Apr 16, 2025, 1:37 AM • 1 Y

Y by dangerousliri

An infinite increasing sequence $a_1 < a_2 < a_3 < \cdots$ of positive integers is called central if for every positive integer $n$ , the arithmetic mean of the first $a_n$ terms of the sequence is equal to $a_n$ .

Show that there exists an infinite sequence $b_1, b_2, b_3, \dots$ of positive integers such that for every central sequence $a_1, a_2, a_3, \dots,$ there are infinitely many positive integers $n$ with $a_n = b_n$ .

This post has been edited 2 times. Last edited by EeEeRUT, Apr 16, 2025, 1:39 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1514 posts

#2 h Apr 16, 2025, 1:56 AM

Y by

We claim $b_i=2i-1$ just happens to work, basically if it happend infinitely many times that $a_i=k$ and $a_{i+1}=k+1$ then we would have that $a_{k+1}=(k+1)^2-k^2=2k+1$ infinitely many times.
Else if it only happend finitely many times then for all $n \ge N$ we would have that $a_{n+1} \ge a_n+2$ however if at any point it happend that $a_m \ge 2m$ then this holds true for all large enough terms and however this would give for some large enough indexes $j,j'$ that $a_j^2-a_j'^2=\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 a contradiction and thus we must always have that $a_m \le 2m-1$ however from summing all we can now trivially see that equality must in fact hold everywhere and then again we have infinite values for which $a_i=b_i$ thus we are done :cool:

:cool:

.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3446 posts

#3 h Apr 16, 2025, 2:24 AM

Y by

We claim $b_i = 2i-1$ works. For all $i$ , we have
$a(a(i)+1) + a(a(i)+2) + \cdots + a(a(i+1)) = a(i+1)^2 - a(i)^2.$ If there are infinitely many integers $i$ for which $a(i)+1 = a(i+1)$ , the above equation implies $a(a(i)+1) = b(a(i)+1)$ , so we're done. Otherwise, for sufficiently large $i$ , we have $a(i+1) \geq a(i)+2$ . Call $i$ non-conforming if $a(a(i)+1), a(a(i)+2), \ldots, a(a(i+1))$ are not consecutive odd integers. For sufficiently large $i$ (where there are no more consecutive terms), this then implies that $a(a(i)+1) < 2a(i)$ and that $a(a(i+1)) > 2a(i+1)-1$ (because of the first equation). So, for any two adjacent blocks, at most one is non-conforming, meaning there are infinitely many conforming blocks and thus infinitely many $i$ for which $a_i = 2i-1$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

117 posts

#4 h Apr 16, 2025, 2:42 AM

Y by

choose $b_n = 2n-1$
if there is infinitely many $a_{n+1}-a_n =1$ there will be infinitely $a_m=2m-1$
assume that there is finitely $a_{n+1}-a_n =1$
or there is $N$ such that all $n>N$ have $a_{n+1}-a_n \geq 2$
consider some $x,y,z,w$ such that $N < a_x = z < a_y =w$
so $a_{z+1}+a_{z+2} + ... + a_{w} = w^2-z^2$
and some calculation will finish the problem . $\square$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

66 posts

#5 h Apr 16, 2025, 2:27 PM

Y by

We say that an index $i$ is cool iff $a_i = 2i-1$ and say that an index $k$ is great iff $a_{k+1} - a_k = 1$
We claimed that $b_i = 2i-1$ works.
Note that $\sum_{j=1}^{a_{k}} a_j = a_k^2$ Also, since the sequence is strictly increasing, we have $a_i \geqslant i$ Claim: If $k$ is great then some index $K > k$ is cool
Proof: Note that if $k$ is great then we have $a_{a_{k+1}} = \sum_{j=1}^{a_{k+1}} a_j - \sum_{j=1}^{a_k} a_j = a_{k+1}^2 - a_k^2 = 2a_{k+1} - 1$ Hence, $a_{k+1}$ is cool. $\blacksquare$

Claim : Suppose that there are at least $2$ cool index, then at least one of the set $G$ of great index or the set $C$ of cool index is an infinity set.
Proof: Suppose $C$ and $G$ is finite, then for some $N$ , we have $a_n +2 \leqslant a_{n+1}$ for any $n > N$ .
Also, let $c_1 < c_2 = \max i \in C$ and $g =\max i \in G$ . By the above claim, we have $c_1> c_2 > g$ , hence, for any $n > c$ , we have $a_n > 2n-1$
Consider, $a_{c_2}^2-a_{c_1}^2=\sum_{j=a_{c_1}+1}^{a_{c_2}} a_j > \sum_{j=a_{c_1}+1}^{a_{c_2}} 2j-1 = (2c_2-1)^2 - (2c_1-1)^2 = a_{c_2}^2 - a_{c_1}^2$ Hence, contradiction. $\blacksquare$

So, we are left to show that at least $2$ cool index exists. Consider the sequence, it must start with $a_1 = 1$ otherwise contradiction.
If $a_2 = 2$ , we finish with the first claim. If $a_2 = 3$ , then $2$ is cool. If $a_2 = 4$ , then $a_3 = 5$ and $a_4 = 6$ , otherwise they violate the sum is over $16$ . Thus, $3$ is cool. Hence, we are done. $\blacksquare$ .

This post has been edited 1 time. Last edited by EeEeRUT, Apr 16, 2025, 2:30 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

66 posts

#6 h Apr 18, 2025, 12:47 AM

Y by

We claim that $b_n = 2n - 1$ , works, i.e., $a_n = 2n-1$ for infinitely many values of $n$ .

Notice that $a_{n+1} - a_n = 1\implies \boxed{a_{a_n+1} = (a_n+1)^2 - a_n^2 = 2(a_n+1)-1}$ .

So we may assume FTSOC that this holds for finitely many values of $n$ . In particular, for some $N$ and all $k \geq N$ it holds that $a_{k+1} - a_k \geq 2$ $(\clubsuit)$ .

Lemma 1: There are arbitrarily large $l$ for which $a_l \leq 2l-1$ .

Proof: Take $k \geq N$ . We have:

$a_{k+1}^2 - a_k^2 = a_{a_k + 1} + a_{a_k+2}+\dots + a_{a_{k+1}}\geq (a_{a_k} + 2) + (a_{a_k} + 4) + \dots + (a_{a_k} + 2(a_{k+1} - a_k))\implies$

$a_{k+1}^2 - a_k^2 \geq (a_{k+1} - a_k)(a_{a_k} + a_{k+1} - a_k + 1)\implies \boxed{a_{a_k} \leq 2a_k - 1} \$ Which proves the claim. $_{\blacksquare}$

Lemma 2: There is an integer $M$ such that for all $k\geq M$ we have $a_{k+1} - a_k = 2$

Proof: Define $f(k) = a_k - 2k$ . By $(\clubsuit)$ we have that $f$ is non-decreasing in $k \geq N$ , but if the lemma was false, $f$ would eventually turn positive, a contradiction by Lemma 1! $_{\blacksquare}$

Now we have $a_{M+1}= a_M +2$ , so:

$(a_M+2)^2 - a_M^2 = a_{a_M+1} + a_{a_M+2} = (a_M + 2(a_M+1-M)) + (a_M + 2(a_M+2-M))\implies$

$4a_M + 4 = 6a_M - 4M + 6\implies\boxed{a_M = 2M-1}$

So inductively we have $a_n = 2n-1$ for all $n\geq M$ and we are done. $_{\blacksquare}$

This post has been edited 7 times. Last edited by Thelink_20, Apr 18, 2025, 1:20 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

42 posts

#7 h Apr 18, 2025, 8:07 AM

Y by

Took me too long, just too long (3 days)

Attachments:

EGMO P2.pdf (37kb)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

930 posts

#8 h Apr 18, 2025, 4:28 PM

Y by

This problem was proposed by Netherlands.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

135 posts

#9 h Apr 19, 2025, 5:11 PM

Y by

Jupiterballs wrote:

Took me too long, just too long (3 days)

Can you explain more the part of the inequality

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

42 posts

#10 h Apr 23, 2025, 1:26 PM

Y by

Dakernew192 wrote:

Jupiterballs wrote:

Took me too long, just too long (3 days)

Can you explain more the part of the inequality

In the same notations as my solutions, we have that $a_{i_1}, a_{i_2} = 2i_1 - 1$ and $2i_2 - 1$ respectively, and by the fact that $a_{j+1} - a_{j} \ge 2$ , we have that all other numbers (say for eg. $a_k$ ) between the sum $\sum_{j=a_{i_2}+1}^{a_{i_1}} a_j$ are greater than $2k-1$ .
The rest is just a sum of numbers

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4 posts

#12 h Yesterday at 12:43 AM

Y by

Through observation, we see that $b_i = 2i -1$ seems promising. Let us try to prove this works.

Note that for any sequence, $a_1 = 1$ since the sequence is strictly increasing. Thus, there will always exist at least one term in the sequence $a$ that is also present in the sequence $b$ .

Then, let us assume that there is a finite number of such terms within the sequence. Let the last term be $a_k = 2k - 1$ . Denote the sum of the first $x$ numbers as $S_k$ .

Case 1: $a_{k+1} = 2k$
Note that, $a_{2k} = S_{2k} - S_{2k-1} = 4k^2 - (4k^2 - 4k + 1) = 4k - 1$ so $a_{2k}$ is part of $b$ and there is a contradiction.

Case 2: $a_{k+1} = 2k + 1$
Note that, $a_{k+1}$ is part of $b$ and there is a contradiction.

Case 3: $a_{k+1} \ge 2k + 2$
If $a_{k+1} \ge 2k + 2$ , then since $a_{k+2} \neq 2k + 3$ (because then it would be a term of $b$ ), $a_{k+2} \ge 2k + 4$ . Then, it is easy to see that if none of these terms are present in $b$ , by induction, we get $a_x > 2x$ for $x > k$ .

Now, $S_{2k - 1} = 4k^2 - 4k + 1$ . However, $S_{2k} = (4k^2 - 4k + 1) + 4k > (2k)^2$ . Let us try to prove $S_x > x^2$ for $x > 2k - 1$ . Assume $S_n > n^2$ . Then, $S_{n + 1} = S_n + a_{n + 1} > n^2 + 2n + 2 > (n + 1)^2$ . Thus, $S_x > x^2$ for $x > 2k - 1$ .

However, for any number $x$ that is a part of sequence $a$ , there exists a number $y$ such that $S_y = x^2$ . So, since $a$ is an infinite sequence that is strictly increasing, $S_x > x^2$ for $x > 2k - 1$ is a contradiction.

Having exhausted all cases, it is impossible for there to be only a finite number of shared terms. Thus, we are done. $\square$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a