Maths Olympiad Prep

Track / Stage 7 / 100 of 300 #2140 of 2604

Problem 2140

National Olympiad second round; IMO P1/P4
Algebra Difficulty 7.3 Prove it Japanese Mathematical Olympiad · Japan

For an integer n≥3n \ge 3, a sequence of integers a1,a2,…,ana_1, a_2, \dots, a_n is called a beautiful sequence if the following conditions are all satisfied.
* 0=a1<a2<⋯<an0 = a_1 < a_2 < \dots < a_n.
* There exists an integer ii such that 1≤i≤n1 \le i \le n and ai=2025a_i = 2025.
* For all integers i,j,ki, j, k with 1≤i<j<k≤n1 \le i < j < k \le n, the inequality ai+ak2≤aj\frac{a_i + a_k}{2} \le a_j holds.
Let NN be the maximum possible length of a beautiful sequence. For beautiful sequences a1,a2,…,aNa_1, a_2, \dots, a_N of length NN, determine the minimum possible value of aNa_N.
Here, the length of a sequence of integers x1,x2,…,xlx_1, x_2, \dots, x_l is ll.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

Let a1,a2,…,ana_1, a_2, \dots, a_n be a beautiful sequence of length nn. Take an integer mm such that am=2025a_m = 2025. Then m≥2m \ge 2 since a1=0a_1 = 0.
We first prove n≤13n \le 13. Let tt be an integer with 1≤t≤n−21 \le t \le n - 2. By applying the third condition to (i,j,k)=(t,t+1,n)(i, j, k) = (t, t+1, n), we obtain
at+an2≤at+1, \frac{a_t + a_n}{2} \le a_{t+1},
which implies
an−at≥2(an−at+1). a_n - a_t \ge 2(a_n - a_{t+1}).
If m=nm = n, repeatedly applying this inequality gives
2025=an−a1≥2(an−a2)≥⋯≥2n−2(an−an−1)≥2n−2, 2025 = a_n - a_1 \ge 2(a_n - a_2) \ge \dots \ge 2^{n-2}(a_n - a_{n-1}) \ge 2^{n-2},
and hence n≤12n \le 12. If m<nm < n, we have
an−a1≥2(an−a2)≥⋯≥2m−2(an−am−1)≥2m−1(an−am), a_n - a_1 \ge 2(a_n - a_2) \ge \dots \ge 2^{m-2}(a_n - a_{m-1}) \ge 2^{m-1}(a_n - a_m),
and
an−am≥2(an−am+1)≥22(an−am+2)≥⋯≥2n−m−1(an−an−1)≥2n−m−1. a_n - a_m \ge 2(a_n - a_{m+1}) \ge 2^2(a_n - a_{m+2}) \ge \dots \ge 2^{n-m-1}(a_n - a_{n-1}) \ge 2^{n-m-1}.
2025=am−a1=(an−a1)−(an−am)≥(2m−1−1)(an−am)≥(2m−1−1)2n−m−1≥2m−2⋅2n−m−1=2n−3\begin{aligned} 2025 &= a_m - a_1 = (a_n - a_1) - (a_n - a_m) \ge (2^{m-1} - 1)(a_n - a_m) \\ &\ge (2^{m-1} - 1)2^{n-m-1} \ge 2^{m-2} \cdot 2^{n-m-1} = 2^{n-3} \end{aligned}
\quad (*)
and so we obtain n≤13n \le 13. Let n=13n = 13. Then the above argument shows n>mn > m. From (∗)(*), we have
2025 ≥(2m−1−1)2n−m−1=2n−2−2n−m−1=211−212−m,\ge (2^{m-1} - 1)2^{n-m-1} = 2^{n-2} - 2^{n-m-1} = 2^{11} - 2^{12-m},
whichimplies$212−m≥23$,andhence$212−m≥32$.Therefore, which implies \$2^{12-m} \ge 23\$, and hence \$2^{12-m} \ge 32\$. Therefore,
a_n = a_m + (a_n - a_m) ≥\ge a_m + 2n−m−12^{n-m-1} = 2025 + 212−m≥2^{12-m} \ge 2057.
Thus,wehave$an≥2057$when$n=13$.Finally,weshowthatthesequence Thus, we have \$a_n \ge 2057\$ when \$n = 13\$. Finally, we show that the sequence
(a_1, a_2, …,a13)\dots, a_{13}) = (0, 1033, 1545, 1801, 1929, 1993, 2025, 2041, 2049, 2053, 2055, 2056, 2057)
is a beautiful sequence of length 13. The first and second conditions are clearly satisfied. We now verify the third condition. We have
(a13(a_{13} - a_1, a13a_{13} - a_2, …,a13−a12)\dots, a_{13} - a_{12}) = (2057, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1),
soforallintegers$t$with$1≤t≤11$,wehave$a13−at≥2(a13−at+1)$.Therefore,forallintegers$1≤i<j<k≤13$,wehave so for all integers \$t\$ with \$1 \le t \le 11\$, we have \$a_{13} - a_t \ge 2(a_{13} - a_{t+1})\$. Therefore, for all integers \$1 \le i < j < k \le 13\$, we have
aj−ai+ak2≥aj−ai+a132=(a13−ai)−2(a13−aj)2≥(a13−ai)−(a13−aj−1)2=aj−1−ai2≥0.\begin{aligned} a_j - \frac{a_i + a_k}{2} &\ge a_j - \frac{a_i + a_{13}}{2} = \frac{(a_{13} - a_i) - 2(a_{13} - a_j)}{2} \\ &\ge \frac{(a_{13} - a_i) - (a_{13} - a_{j-1})}{2} = \frac{a_{j-1} - a_i}{2} \\ &\ge 0. \end{aligned}

This confirms the third condition.
Therefore, the maximum value of the length of a beautiful sequence is 13 and for beautiful sequences a1,a2,…,a13a_1, a_2, \dots, a_{13} of length 13, the minimum value of a13a_{13} is 2057.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.