Maths Olympiad Prep

Library / /10 of 16

Algebra Difficulty 7.3 National olympiad, round 2 Prove it Japan

For an integer n3n \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 1in1 \le i \le n and ai=2025a_i = 2025.
* For all integers i,j,ki, j, k with 1i<j<kn1 \le i < j < k \le n, the inequality ai+ak2aj\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.

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 m2m \ge 2 since a1=0a_1 = 0.
We first prove n13n \le 13. Let tt be an integer with 1tn21 \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+an2at+1, \frac{a_t + a_n}{2} \le a_{t+1},
which implies
anat2(anat+1). a_n - a_t \ge 2(a_n - a_{t+1}).
If m=nm = n, repeatedly applying this inequality gives
2025=ana12(ana2)2n2(anan1)2n2, 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 n12n \le 12. If m<nm < n, we have
ana12(ana2)2m2(anam1)2m1(anam), 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
anam2(anam+1)22(anam+2)2nm1(anan1)2nm1. 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=ama1=(ana1)(anam)(2m11)(anam)(2m11)2nm12m22nm1=2n3\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 n13n \le 13.
Let n=13n = 13. Then the above argument shows n>mn > m. From ()(*), we have

2025 (2m11)2nm1=2n22nm1=211212m,\ge (2^{m-1} - 1)2^{n-m-1} = 2^{n-2} - 2^{n-m-1} = 2^{11} - 2^{12-m},
whichimplies$212m23$,andhence$212m32$.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 + 2nm12^{n-m-1} = 2025 + 212m2^{12-m} \ge 2057.
Thus,wehave$an2057$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, ,a13a12)\dots, a_{13} - a_{12}) = (2057, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1),
soforallintegers$t$with$1t11$,wehave$a13at2(a13at+1)$.Therefore,forallintegers$1i<j<k13$,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
ajai+ak2ajai+a132=(a13ai)2(a13aj)2(a13ai)(a13aj1)2=aj1ai20.\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.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.