Maths Olympiad Prep

Library / /109 of 158

Algebra Difficulty 6.3 National Olympiad Prove it Estonia

There are 125125 distinct positive integers in a row in such a way that among every three consecutive numbers the second one is larger than the arithmetic mean of the first and the third one. Find the largest number in the row, given that it is as small as possible under such conditions.

Solution

Let the numbers in a row be a1,a2,,a125a_1, a_2, \dots, a_{125}. By conditions, we have ai+1>ai+ai+22a_{i+1} > \frac{a_i + a_{i+2}}{2} for every i=1,2,,123i = 1, 2, \dots, 123, which is equivalent to ai+1ai>ai+2ai+1a_{i+1} - a_i > a_{i+2} - a_{i+1}. Denoting di=ai+1aid_i = a_{i+1} - a_i, we have d1>d2>>d124d_1 > d_2 > \dots > d_{124}.

Let ama_m be the largest among a1,,a125a_1, \dots, a_{125}; then d1,d2,,dm1d_1, d_2, \dots, d_{m-1} are positive and dm,dm+1,,d124d_m, d_{m+1}, \dots, d_{124} are negative. If both 11 and 1-1 occurred among the differences d1,d2,,d124d_1, d_2, \dots, d_{124}, then they should be consecutive, i.e., di=1d_i = 1 and di+1=1d_{i+1} = -1 for some ii, whence ai+1=ai1a_{i+1} = a_{i-1}. Contradiction to the assumption that the given numbers are distinct shows that either 11 or 1-1 is missing among the differences. W.l.o.g., assume that 11 is missing (if 1-1 is missing, we can reverse the numeration of the given numbers).

Then am=a1+(d1+d2++dm1)1+(m+(m1)++2)=1+2++ma_m = a_1 + (d_1 + d_2 + \dots + d_{m-1}) \ge 1 + (m + (m-1) + \dots + 2) = 1 + 2 + \dots + m and am=a125(dm+dm+1++d124)1+(1+2++(125m))a_m = a_{125} - (d_m + d_{m+1} + \dots + d_{124}) \ge 1 + (1 + 2 + \dots + (125 - m)). Among numbers mm and 125m125 - m, one is at least 6363, whence the previously established inequalities imply am1+2++63a_m \ge 1 + 2 + \dots + 63.

On the other hand, taking a1=1a_1 = 1 and di=64id_i = 64 - i, 1i621 \le i \le 62, and di=62id_i = 62 - i, 63i12463 \le i \le 124, the largest number a63a_{63} equals 1+2++631 + 2 + \dots + 63, while all numbers aia_i are positive, as 1=a1<a2<<a631 = a_1 < a_2 < \dots < a_{63} and a63>a64>>a125=(1+2++63)(1+2++62)=63a_{63} > a_{64} > \dots > a_{125} = (1 + 2 + \dots + 63) - (1 + 2 + \dots + 62) = 63. All these numbers are distinct, since for every i=64,65,,125i = 64, 65, \dots, 125, ai=(1+2++63)(1+2++(i63))=(i62)+(i61)++63=a127i1a_i = (1 + 2 + \dots + 63) - (1 + 2 + \dots + (i - 63)) = (i - 62) + (i - 61) + \dots + 63 = a_{127 - i} - 1, whence aia_i lies strictly between a126ia_{126 - i} and a127ia_{127 - i}. Consequently, the largest number written in the row is 1+2++631 + 2 + \dots + 63, i.e., 20162016.

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.