48th International Mathematical Olympiad Vietnam 2007 Shortlisted Problems with Solutions

(a) Let $1\le p\le q\le r\le n$ be indices for which $$d=d_q,a_p=\max \{a_j:1\le j\le q\},a_r=\min \{a_j:q\le j\le n\}$$ and thus $d=a_p-a_r$. (These indices are not necessarily unique.) For arbitrary real numbers $x_1\le x_2\le \dots \le x_n$, consider just the two quantities $\left|x_p-a_p\right|$ and $\left|x_r-a_r\right|$. Since $$\left(a_p-x_p\right)+\left(x_r-a_r\right)=\left(a_p-a_r\right)+\left(x_r-x_p\right)\ge a_p-a_r=d,$$ we have either $a_p-x_p\ge \frac{d}{2}$ or $x_r-a_r\ge \frac{d}{2}$. Hence, $$\max \{\left|x_i-a_i\right|:1\le i\le n\}\ge \max \{\left|x_p-a_p\right|,\left|x_r-a_r\right|\}\ge \max \{a_p-x_p,x_r-a_r\}\ge \frac{d}{2}$$

(b) Define the sequence $\left(x_k\right)$ as $$x_1=a_1-\frac{d}{2},x_k=\max \{x_{k-1},a_k-\frac{d}{2}\}\text{ for }2\le k\le n.$$ We show that we have equality in (1) for this sequence. By the definition, sequence ( $x_k$ ) is non-decreasing and $x_k-a_k\ge -\frac{d}{2}$ for all $1\le k\le n$. Next we prove that $$\begin{array}{c}{x}_k-a_k\le \frac{d}{2}\text{ for all }1\le k\le n\end{array}\text{\hspace{1em}(2)}$$ Consider an arbitrary index $1\le k\le n$. Let $\ell \le k$ be the smallest index such that $x_k=x_{\ell }$. We have either $\ell =1$, or $\ell \ge 2$ and $x_{\ell }>x_{\ell -1}$. In both cases, $$\begin{array}{c}{x}_k=x_{\ell }=a_{\ell }-\frac{d}{2}\end{array}\text{\hspace{1em}(3)}$$ Since $$a_{\ell }-a_k\le \max \{a_j:1\le j\le k\}-\min \{a_j:k\le j\le n\}=d_k\le d$$ equality (3) implies $$x_k-a_k=a_{\ell }-a_k-\frac{d}{2}\le d-\frac{d}{2}=\frac{d}{2}$$ We obtained that $-\frac{d}{2}\le x_k-a_k\le \frac{d}{2}$ for all $1\le k\le n$, so $$\max \{\left|x_i-a_i\right|:1\le i\le n\}\le \frac{d}{2}$$ We have equality because $\left|x_1-a_1\right|=\frac{d}{2}$.

---

Alternative solution.

We present another construction of a sequence ( $x_i$ ) for part (b). For each $1\le i\le n$, let $$M_i=\max \{a_j:1\le j\le i\}\text{ and }{m}_i=\min \{a_j:i\le j\le n\}.$$ For all $1\le i<n$, we have $$M_i=\max \{a_1,\dots ,a_i\}\le \max \{a_1,\dots ,a_i,a_{i+1}\}=M_{i+1}$$ and $$m_i=\min \{a_i,a_{i+1},\dots ,a_n\}\le \min \{a_{i+1},\dots ,a_n\}=m_{i+1}.$$ Therefore sequences ( $M_i$ ) and ( $m_i$ ) are non-decreasing. Moreover, since $a_i$ is listed in both definitions, $$m_i\le a_i\le M_i$$ To achieve equality in (1), set $$x_i=\frac{M_i+m_i}{2}$$ Since sequences ( $M_i$ ) and ( $m_i$ ) are non-decreasing, this sequence is non-decreasing as well. From $d_i=M_i-m_i$ we obtain that $$-\frac{d_i}{2}=\frac{m_i-M_i}{2}=x_i-M_i\le x_i-a_i\le x_i-m_i=\frac{M_i-m_i}{2}=\frac{d_i}{2}$$ Therefore $$\max \{\left|x_i-a_i\right|:1\le i\le n\}\le \max \{\frac{d_i}{2}:1\le i\le n\}=\frac{d}{2}$$ Since the opposite inequality has been proved in part (a), we must have equality.