Let $a_1,a_2,\dots,a_{2017}$ be reals satisfied $a_1=a_{2017}$, $|a_i+a_{i+2}-2a_{i+1}|\le 1$ for all $i=1,2,\dots,2015$. Find the maximum value of $\max_{1\le i<j\le 2017}|a_i-a_j|$.
Problem
Source: CSMO 2017 Grade 10 Problem 4
Tags: algebra, maximum value
28.07.2018 17:25
Bump any solution
18.10.2021 03:26
Motivation: note that the difference of difference of the sequence changes by at most 1, hence the sequence has some sort of quadratic behaviour. Consider a "graph" of $a_i$, the difference would obviously be larger if the whole thing was one curve instead of breaking up into multiple curves, cos quadratic. Similar to the question of how to maximise $a_1^2+a_2^2+...+a_n^2$ given a fixed $\sum a_i$. Solution: Part 1: Let $b_i=a_i-a_{i+1}$. From the given condition, $|b_i-b_{i+1}|\le 1$ and $b_1+b_2+ \cdots +b_{2016}=0$. Note that for all $2\le i \le 2015$, $|b_i|\le 1007$ else you cannot "reach 0 on time". Part 2: Consider a sequence of length $t$ that satisfies the condition. Assume that $a_1=a_t=0$ by shifting. We show that the maximum possible value of $|a_i|$ is $\frac{(i-1)(t-i)}{2}$. Proof. Basically, if a number grows too big, the $b_i$ has to start large, and won't make $a_t=0$ in time. For a proper proof: WLOG $i\le \frac{t+1}{2}$, $a_i>\frac{(i-1)(t-i)}{2}$. Then, $(b_{i-1}+(i-2))+(b_{i-1}+(i-3)+...+b_{i-1}\ge b_1+b_2+...+b_{i-1}=a_i>\frac{(i-1)(t-i)}{2}\implies 2i-2+2b_{i-1}>t$. At the same time $-\frac{(i-1)(t-i)}{2}>b_i+b_{i+1}+...+b_{t-1}\ge (b_{i-1}-1)+(b_{i-1}-2)+...+(b_{i-1}-(t-i)) \implies t>2b_{i-1}+2i-2$, a contradiction. Part 3: We go back to the main problem, assuming that $a_1=a_{2017}=0$. We define $a_L$ to be the largest number (>0) and $a_S$ to be the smallest number (<0). If $a_L$ or $a_S$ dosent exist, meaning the entire sequence is non-negative or non-negative, then from part 2 we find the answer to be $\max \frac{(i-1)(2017-i)}{2}$ which obviously occurs when $i=1009$, giving the answer $508032$. Now assume that $a_L$ and $a_S$ exist, and WLOG that $L<S$. Then, the sequence must cross between positive to negative at some point. Suppose $a_t\ge 0$ and $a_{t+1}\le 0$ (Note $2\le t \le 2015$). By part 2, the maximum possible value of $a_L$ is $\le a_t+\frac{(\frac{t+1}{2}-1)(t-\frac{t+1}{2})}{2}=a_t+ \frac{(t-1)^2}{8}$. Similarly, the minimum possible value of $a_S$ is $\ge a_{t+1}-\frac{(2016-t)^2}{8}$ Thus, $a_L-a_S\le (a_t-a_{t+1})+\frac{(t-1)^2+(2016-t)^2}{8}\le b_t+\frac{(2015-1)^2+(2016-2015)^2}{8}=b_t+507025=508032+(b_t-1007)$. However, $b_t$ obviously cannot be $\ge 1007$ by part 1 (note $2\le t \le 2015$). Hence, the answer is $508032$, achievable by $b_1=1007.5, b_2=1006.5, ..., b_{2016}=-1007.5$. Hope a diagram will help:
Attachments:
