Maths Olympiad Prep

Library / /2 of 6

Algebra Difficulty 8.8 Shortlist Prove it Vietnam

Given 2017 positive real numbers a1,a2,,a2017a_1, a_2, \dots, a_{2017}. For each positive integer n>2017n > 2017, let
an=max{ai1ai2ai3i1+i2+i3=n,1i1i2i3n1}. a_n = \max\{a_{i_1} a_{i_2} a_{i_3} \mid i_1 + i_2 + i_3 = n, 1 \le i_1 \le i_2 \le i_3 \le n-1\}.
Prove there exists some positive integers m2017m \le 2017 and N>4mN > 4m such that anan4m=an2m2a_n a_{n-4m} = a_{n-2m}^2 for every n>Nn > N.

Solution

For every n>0n > 0, let bn=lnanb_n = \ln a_n. We can reduce the problem to: Given 2017 reals b1,b2,,b2017b_1, b_2, \dots, b_{2017}. For every n>2017n > 2017, let
bn=max{bi1+bi2+bi3i1+i2+i3=n,1i1i2i3n1}. b_n = \max\{b_{i_1} + b_{i_2} + b_{i_3} \mid i_1 + i_2 + i_3 = n, 1 \le i_1 \le i_2 \le i_3 \le n-1\}.
Prove there exist positive integers m2017m \le 2017 and N>4mN > 4m such that bn+bn4m=2bn2mb_n + b_{n-4m} = 2b_{n-2m} for every n>Nn > N.

Consider \ell (120171 \le \ell \le 2017) such that b=max{bii1i2017}\frac{b_\ell}{\ell} = \max\left\{\frac{b_i}{i} \mid 1 \le i \le 2017\right\}. We have the following statement:

Claim 1. For every nZ+n \in \mathbb{Z}^+:
bnnb. \frac{b_n}{n} \le \frac{b_\ell}{\ell}.
Proof. We prove by induction on nn. The statement is clearly true for n2017n \le 2017 by the definition of \ell. We consider the case n>2017n > 2017. Assume it is true for all k<nk < n. From the definition of bnb_n, there exist j1,j2,j3Nj_1, j_2, j_3 \in \mathbb{N}^* satisfying j1+j2+j3=nj_1 + j_2 + j_3 = n such that
bn=bj1+bj2+bj3. b_n = b_{j_1} + b_{j_2} + b_{j_3}.
Using the induction hypothesis, we have
bnj1b+j2b+j3b=nb, b_n \le j_1 \cdot \frac{b_\ell}{\ell} + j_2 \cdot \frac{b_\ell}{\ell} + j_3 \cdot \frac{b_\ell}{\ell} = n \cdot \frac{b_\ell}{\ell},
so bnnb\frac{b_n}{n} \le \frac{b_\ell}{\ell}. Therefore the statement is also true for nn. The claim has proven.

Now, for every positive integer nn, let cn=nbbnc_n = n b_\ell - \ell b_n then from the above claim we have cn0c_n \ge 0 for every nn. We also have, for n2017n \ge 2017:
cn+2=(n+2)bbn+2(n+2)b(bn+b+b)=nbbn=cn. \begin{aligned} c_{n+2\ell} &= (n+2\ell)b_\ell - \ell b_{n+2\ell} \\ &\le (n+2\ell)b_\ell - \ell(b_n + b_\ell + b_\ell) \\ &= n b_\ell - \ell b_n = c_n. \end{aligned}
Hence
cn+2kcn+2(k1)cn,n2017,k1. c_{n+2k\ell} \le c_{n+2(k-1)\ell} \le \dots \le c_n, \quad \forall n \ge 2017, k \ge 1.
Let xx be the smallest positive integer such that 2x>20172x\ell > 2017 and set
M=max{ci1i4x1}. M = \max\{c_i \mid 1 \le i \le 4x\ell - 1\}.
Then, for every n>2xn > 2x\ell, set n=2kx+rn = 2kx\ell + r (with 0r<2x0 \le r < 2x\ell), we have
cncr+2(k1)xcr+2(k2)xcr+2xM. c_n \le c_{r+2(k-1)x\ell} \le c_{r+2(k-2)x\ell} \le \dots \le c_{r+2x\ell} \le M.
We have the following statements:

Claim 2. For every positive integer nn, there exist natural numbers s1,s2,,s2017s_1, s_2, \dots, s_{2017} such that
cn=s1c1+s2c2++s2017c2017. c_n = s_1 c_1 + s_2 c_2 + \dots + s_{2017} c_{2017}.
Proof. We prove by induction on nn. The statement is clearly true for n2017n \le 2017 (just choose sn=1s_n = 1 and si=0s_i = 0 with ini \ne n). We just need to consider the case n>2017n > 2017 is sufficient. Suppose it is true for k<nk < n. From the definition of bnb_n, we deduce
cn=min{ci1+ci2+ci31i1i2i3n1,i1+i2+i3=n},n>2017. c_n = \min\{c_{i_1} + c_{i_2} + c_{i_3} \mid 1 \le i_1 \le i_2 \le i_3 \le n-1, i_1 + i_2 + i_3 = n\}, \quad \forall n > 2017.
Thus there exist j1,j2,j3Nj_1, j_2, j_3 \in \mathbb{N}^* satisfying j1+j2+j3=nj_1 + j_2 + j_3 = n such that
cn=cj1+cj2+cj3. c_n = c_{j_1} + c_{j_2} + c_{j_3}.
By the induction hypothesis, there exist natural numbers
u1,u2,,u2017,v1,v2,,v2017,w1,w2,,w2017 u_1, u_2, \dots, u_{2017}, v_1, v_2, \dots, v_{2017}, w_1, w_2, \dots, w_{2017}
such that
cj1=u1c1+u2c2++u2017c2017,cj2=v1c1+v2c2++v2017c2017,cj3=w1c1+w2c2++w2017c2017. \begin{align*} c_{j_1} &= u_1 c_1 + u_2 c_2 + \dots + u_{2017} c_{2017}, \\ c_{j_2} &= v_1 c_1 + v_2 c_2 + \dots + v_{2017} c_{2017}, \\ c_{j_3} &= w_1 c_1 + w_2 c_2 + \dots + w_{2017} c_{2017}. \end{align*}
Therefore, we have
cn=s1c1+s2c2++s2017c2017, c_n = s_1 c_1 + s_2 c_2 + \dots + s_{2017} c_{2017},
where si=ui+vi+wis_i = u_i + v_i + w_i for 1i20171 \le i \le 2017. Hence the statement is also true for nn. The claim has proven.

Claim 3. The sequence (cn)(c_n) get only finite values.

Proof. This statement is inferred directly from the boundedness of cnc_n and the result of above claim.

Now, since cnc_n get only finite values and
cn+2kxcn+2(k1)xcn c_{n+2kx\ell} \le c_{n+2(k-1)x\ell} \le \dots \le c_n
for every n2017n \ge 2017 so there exists N1N_1 big enough such that cn=cn2xc_n = c_{n-2x\ell} for every n>N1n > N_1. Then, we have
nbbn=(n2x)bbn2x,n>N1, n b_{\ell} - \ell b_n = (n - 2x\ell) b_{\ell} - \ell b_{n-2x\ell}, \quad \forall n > N_1,
or
bn=2b+bn2x,n>N1. b_n = 2b_{\ell} + b_{n-2x\ell}, \quad \forall n > N_1.
Then, we conclude that
bn2x=2b+bn4x,n>N1+2x. b_{n-2x\ell} = 2b_{\ell} + b_{n-4x\ell}, \quad \forall n > N_1 + 2x\ell.
From two above results, we get
bn+bn4x=2bn2x,n>N1+2x. b_n + b_{n-4x\ell} = 2b_{n-2x\ell}, \quad \forall n > N_1 + 2x\ell.
Choose N=N1+2xN = N_1 + 2x\ell and m=xm = x\ell, we have the desired result.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.