$ (a)$ we suppose that $ MAX\{|x_{i}-a_{i}|\ |\ 1\le i\le n\}<\frac{d}{2}$ so $ \forall i\in [|1,n|]: \ x_{i}+d/2>a_{i}>x_{i}-d/2$ then $ \forall i\in [|1,n|]: \ d_{i}<(x_{i}+d/2)-(x_{i}-d/2)=d$ gives $ d=MAX\{d_{i}|\ 1\le i\le n\}<d$ (impossible)

1a Suppose on the contrary, $ |x_{i}-a_{i}|<\frac{d}{2}$ for every $ 1\leq i\leq n$. Note that $ d_{i}=a_{k}-a_{l}$ for some $ 1\leq k\leq i$ and $ i\leq l\leq n$. (So in particular $ k\leq l$ and $ x_{k}-x_{l}\leq 0$) Now $ d_{i}=(a_{k}-x_{k})+(x_{k}-x_{l})+(x_{l}-a_{l})$ $ \leq |a_{k}-x_{k}|+|x_{l}-a_{l}|$ $ <d$ Since this holds for every $ i$, then $ \max\{d_{i}\}<d$ (contradiction!)

For Part b we make the $ x_{k}$ like this: Put $ x_{i}=\max\{a_{i}|1\leq i\leq k\}-\frac{d}{2}$. We can easily check the conditions.

1a) $ d = a_{k} - a_{l}$ $ l\ge k$ then $ max(|x_{i} - a_{i}|)\geq 0.5(|a_{k} - x_{k}| + |x_{l} - a_{l}|)\ge0.5(|a_{k} - a_{l} + x_{l} - x_{k}|)\ge0.5d$ 1b) by induction for $ n = 1$ easy one let $ d = a_{k} - a_{l}$ $ l\ge k$ let $ (y_{1},y_{2},...y_{l - 1})$ be such that equality holds for$ (a_{1},a_{2},...a_{l - 1})$ and $ (z_{l + 1},...,z_{n})$ be such that equality holds for$ (a_{l + 1},a_{2},...a_{n})$ just put ${ x_{i} = min(y_{i},(a_{k} + a_{l})/2})$ for $ i\le k$ $ x_{i} = (a_{k} + a_{l})/2$ for $ i\in < k,l >$ $ x_{i} = max({z_{i},(a_{k} + a_{l})/2})$ for rest it's easy to see that that $ x_{i}$ is good

Greedy solution: $ x_{1}=a_{1}-d/2$ $ x_{i}=max( a_{i}-d/2, x_{i-1})$

A very nice problem! Maybe the best problem #1 of the last five years... ==================================================== It is convenient to understand the following related problem: Given are n intervals I_1,...,I_n, where I_k=[L_k;R_k] for k=1..n. Under which conditions do there exist real numbers x_1,...,x_n such that (i) x_1 <= x_2 <= x_3 <= ... <= x_n (ii) x_k in I_k for k=1..n. ==================================================== A necessary condition for a solution of the related problem is that (**) for all i<j, the interval I_i does not lie strictly to the right of I_j. ==================================================== Suppose that the related problem possesses a solution, and consider the lexicographically smallest solution. It can be shown (easy, easy) that this lexicographically smallest solution is found by the following greedy algorithm: 1. Fix x_1 at the left endpoint L_1 of interval I_1 2. For k=2..n fix x_k as the maximum of x_{k-1} and L_k. It can be shown furthermore that the greedy algorithm succeeds, whenever the necessary condition (**) is fulfilled. Therefore, (**) is necessary and sufficient. ==================================================== The IMO problem considers the special case of the above problem where I_k = [a_k-d; a_k+d]. In this case, condition (**) boils down to condition (*) in the IMO problem. Part (a) settles necessity, and part (b) sufficiency.

This problem is very easy. Just draw some kind of diagram of this and the solution is obvious.

yes, I like goblin's solution. i think it applies to all other problems.

yes it could. But seriously could you please elaborate on that Goblin?

color wrote: But seriously could you please elaborate on that Goblin? Well, I just wanted to say that if you draw graphs of functions $ a: \mathbb N\rightarrow \mathbb R$ and $ x: \mathbb N\rightarrow\mathbb R$ it's very easy to find a solution.

yeh I also think so. In this problem configuration of the idea is very important to get a clear solution

Goblin wrote: This problem is very easy. Just draw some kind of diagram of this and the solution is obvious. shunka wrote: yes, I like goblin's solution. i think it applies to all other problems. But Goblin did not give a solution, did he?

All I tried to say is that Goblin's solution applies word for word (without any changes) to any problem in this competition as well as to any other problem. As such, it deserves our special attention and prise. Of course, (s)he could have been more precise and offer more specifics in the crucial step saying "draw some kind of diagram", but if (s)he did that then the solution would lose its wast generality and we would not be able to use it for all other problems. Thus, the solution is perfect just as presented by the author.

Well, to help elaborate on the drawing a diagram method... Consider some $ a_{j}$, $ a_{k}$ such that $ a_{j}-a_{k}=d, j \le k$. Then for $ j \le i \le k$, $ a_{j}\le a_{i}\le a_{k}$, and for $ i \le j$, $ a_{i}\le a_{j}$, and for $ k \le i$, $ a_{k}\le a_{i}$. Thus, if you plot it in the xy plane, you get a sort of "bent pipe" like shape. And then it's clear if you look in the middle region where the "pipe" is going horizontally that $ a_{j}-x_{j}$ and $ a_{k}-x_{k}$ differ by at least $ d$, giving part a. From there, it's also clear that the equality case occurs when $ x_{j}=x_{j+1}=...=x_{k}=\frac{a_{j}+a_{k}}{2}$. From there, you kinda deduce after some thought experiments the bahavior of $ x_{i}$ otherwise, and get $ x_{i}=\text{max}\{x_{i-1}, a_{i}-\frac{d}{2}\}$

maybe found by any others, but here's my answer simplified: case of $ d=0$, $ a_{i}$ is monotonically increasing and we let $ x_{i}=a_{i}$ otherwise, let $ d=a_{k}-a_{l}$. then $ x_{i}=max(a_{1},\cdots,a_{i})-\frac{d}{2}$ for $ i < k$, $ x_{i}=min(a_{i},\cdots,a_{n})+\frac{d}{2}$ for $ i > l$, and $ x_{i}=\frac{a_{k}+a_{l}}{2}$ for $ k \leq i \leq l$.

it is not hard problem but it is good for imo1

Interesting Very similar problem appears at http://www.ajorza.org/wimo/index.php/Romania_Pre-IMO

Let $i\in \lbrace 1,2,...,n \rbrace $ and consider $d_i=a_t-a_r $ for $t\leq i\leq r$ and $ a_t\geq a_i\geq a_r$ \[max \{ |x_{i} - a_{i}| \mid 1 \leq i \leq n \} \geq \frac{|x_t-a_t|+|x_r-a_r|}{2} \geq \frac{|a_t-a_r+x_r-x_t|}{2}\] \[=\frac{a_t-a_r+x_r-x_t}{2} \geq \frac{d_i}{2}\] so \[(\forall i\in \lbrace 1,2,...,n \rbrace) \ max \{ |x_{i} - a_{i}| \mid 1 \leq i \leq n \} \geq \frac{d_i}{2}\] hence \[max \{ |x_{i} - a_{i}| \mid 1 \leq i \leq n \} \geq \frac{max_{1\leq i\leq n} d_i}{2}=\frac{d}{2}\]

I probably made a small error somewhere; the proof should be right, though. Note that the case where $a_1\le a_2\le \dots \le a_n$ is trivial. Then note that $d>0$ is just equal to the maximal value of $a_i-a_j$ over all $1\le i<j\le n$. Consider some two fixed numbers $p$ and $q$ such that $p<q$ and $a_p-a_q=d$. Then at least one of $|x_p-a_p|$ and $|x_q-a_q|$ is at least $\frac{d}{2}$, so the first part is proven. For the second part, we give an algorithm to construct all $x_i$ for $i>q$, the case where $i<p$ being symmetric. Consider an empty set $S$. We iterate through $a_i$ for $p\le i\le n$, using the following rules: If adding $a_i$ would not cause $\text{max}(S)-\text{min}(S)$ to exceed $d$, then add $a_i$. Otherwise, for all $x_i$ corresponding to the elements in $S$, set each one equal to $\frac{\text{max}(S)+\text{min}(S)}{2}$. Then clear $S$ and add $a_i$. At the end of the algorithm, perform the second step. Now, we show that this works. Clearly $(*)$ is satisfied; it suffices to show that $x_p\le x_{p+1}\le \dots \le x_n$. Suppose otherwise. Then suppose there exists a number $i$ such that $p\le i\le n$ and $x_{i-1} > x_i$. Then let the set $S$ at the second step of our algorithm for $x_{i-1}$ and $x_i$ be $S_1$ and $S_2$. We must have $\text{max}(S_2)>\text{min}(S_1)+d$ thus $x_i>\text{min}(S_1)+\frac{d}{2}$. But then $x_{i-1}\le \text{min}(S_1)+\frac{d}{2}$ which is a contradiction.

ISL Marabot solve Let, $b_{i} = \max \{ a_{j}\mid 1 \leq j \leq i \} $ and, $c_i =\min \{ a_{j}\mid i \leq j \leq n \}$ $\textbf{Part (a):}$ Here, clearly, $d_i \geq 0$ as $b_i \geq a_i \geq c_i \ \forall \ i \in \{1,2,\dots,n\}$. Now, if $d=0$ then it's trivial. So lets assume that $d=d_k > 0$ for some $1\leq k \leq n.$ Let, $a_p$ be the maximum among $a_1,\dots, a_k$ and $a_q$ is the minimum among $a_k,\dots, a_n$. Now, $p < q$ as $d\neq 0$. So, $x_p \leq x_q$ but $a_p > a_q$. So clearly one of $|a_p-x_p|, |a_q-x_q|$ will be atleast, $\dfrac {a_p-a_q}{2} = \dfrac d 2. \ \ \ \ \blacksquare$ $\textbf{Part (b):}$ We, take $x_i = \dfrac{b_i+c_i} 2$. This sequence is non-decreasing as both $(b_i)$ and $(c_i)$ are non-decreasing. Now, $|a_i-x_i| \leq \dfrac {d_i} 2$ as, $b_i \geq a_i \geq c_i \ \forall \ i \in \{1,2,\dots,n\}$. So, $\max \{ |x_{i} - a_{i}| \mid 1 \leq i \leq n \}\leq \frac {d}{2}$. And this along with the result from $\boxed{\text{Part (a)}}$ gives, $\max \{ |x_{i} - a_{i}| \mid 1 \leq i \leq n \} = \frac {d}{2}. \ \ \ \ \blacksquare$

(a) Define the descent of an ordered pair $(i,j)$ with $i<j$ as $\max(0, a_i-a_j)$. Clearly, $d$ is the largest descent over all ordered pairs $(i,j)$. Suppose $(i_m,j_m)$ achieves a descent of $d$. Since $x_{i_m}\leq x_{j_m}$, the best we can do is $x_{i_m}=x_{j_m}=\frac{a_{i_m}+a_{j_m}}{2},$ which causes a maximum difference of $d/2$. (b) We break up the sequence $a$ into groups, such that a new group starts if and only if the current value in the sequence is larger than all terms before it. For each group $G$ corresponding to indices $p$ through $q$, we assign $x_i=\frac{\max(G)-\min(G)}{2}$ for all $p\leq i \leq q$ if this fits $x$ being increasing, otherwise we use the same value as we did in the last group. This guarantees that $|a_i-x_i|\leq d/2$, so we are done.

In what follows, we index functionally and from \(0\). For natural \(\text{k}\), we mean by \(\text{i}\colon\text{k}\) that \(\text{i}\in\left\{0,\dots,\text{k}-1\right\}\). (a) Remark that \begin{align*}\max_{\text{i}\colon\text{n}}\left\{\max_{\text{j}_{0}\colon\text{i}+1}\left\{a\left(\text{j}_{0}\right)\right\}-\min_{\text{j}_{1}\colon\text{n}-\text{i}}\left\{a\left(\text{i}-1+\text{j}_{1}\right)\right\}\right\}\ &=\ \max_{\text{i}\colon\text{n}}\left\{\max_{\text{j}_{0}\colon\text{i}+1,\ \text{j}_{1}\colon\text{n}-\text{i}}\left\{a\left(\text{j}_{0}\right)-a\left(\text{i}-1+\text{j}_{1}\right)\right\}\right\}\\ &=\ \max_{\text{i}\colon\text{n},\ \text{j}_{0}\colon\text{i}+1,\ \text{j}_{1}\colon\text{n}-\text{i}}\left\{a\left(\text{j}_{0}\right)-a\left(\text{i}-1+\text{j}_{1}\right)\right\}\\ &=\ \max_{\substack{\text{j}_{0}\colon\text{n},\ \text{j}_{1}\colon\text{n} \\ \text{j}_{0}\ \leq\ \text{j}_{1}}}\left\{a\left(j_{0}\right)-a\left(j_{1}\right)\right\}.\end{align*}In particular, for a maximizing pair \(\left(\text{j}_{0},\text{j}_{1}\right)=\left(\text{J}_{0},\text{J}_{1}\right)\) and any increasing sequence \(x\left(0\right)\leq\dots\leq x\left(\text{n}-1\right)\) we have that \begin{align*}\left|a\left(\text{J}_{0}\right)-x\left(\text{J}_{0}\right)\right|\ +\ \left|a\left(\text{J}_{1}\right)-x\left(\text{J}_{1}\right)\right|\ &\geq\ \left(a\left(\text{J}_{0}\right)-x\left(\text{J}_{0}\right)\right)\ -\ \left(a\left(\text{J}_{1}\right)-x\left(\text{J}_{1}\right)\right)\\ &=\ \left(a\left(\text{J}_{0}\right)-a\left(\text{J}_{1}\right)\right)\ +\ \left(x\left(\text{J}_{1}\right)-x\left(\text{J}_{0}\right)\right)\\ &=\ \max_{\substack{\text{j}_{0}\colon\text{n},\ \text{j}_{1}\colon\text{n} \\ \text{j}_{0}\ \leq\ \text{j}_{1}}}\left\{a\left(\text{j}_{0}\right)-a\left(\text{j}_{1}\right)\right\}\ +\ \left(x\left(\text{J}_{1}\right)-x\left(\text{J}_{0}\right)\right) \\ &=\ \max_{\text{i}\colon\text{n}}\left\{\max_{\text{j}_{0}\colon\text{i}+1}\left\{a\left(\text{j}_{0}\right)\right\}-\min_{\text{j}_{1}\colon\text{n}-\text{i}}\left\{a\left(\text{i}-1+\text{j}_{1}\right)\right\}\right\}\ +\ \left(x\left(\text{J}_{1}\right)-x\left(\text{J}_{0}\right)\right)\\ &\geq\ \max_{\text{i}\colon\text{n}}\left\{\max_{\text{j}_{0}\colon\text{i}+1}\left\{a\left(\text{j}_{0}\right)\right\}-\min_{\text{j}_{1}\colon\text{n}-\text{i}}\left\{a\left(\text{i}-1+\text{j}_{1}\right)\right\}\right\}\end{align*}whence either \[\left|a\left(\text{J}_{0}\right)-x\left(\text{J}_{0}\right)\right|\ \geq\ \frac{1}{2}\max_{\text{i}\colon\text{n}}\left\{\max_{\text{j}_{0}\colon\text{i}+1}\left\{a\left(\text{j}_{0}\right)\right\}-\min_{\text{j}_{1}\colon\text{n}-\text{i}}\left\{a\left(\text{i}-1+\text{j}_{1}\right)\right\}\right\} \]or \[\left|a\left(\text{J}_{1}\right)-x\left(\text{J}_{1}\right)\right|\ \geq\ \frac{1}{2}\max_{\text{i}\colon\text{n}}\left\{\max_{\text{j}_{0}\colon\text{i}+1}\left\{a\left(\text{j}_{0}\right)\right\}-\min_{\text{j}_{1}\colon\text{n}-\text{i}}\left\{a\left(\text{i}-1+\text{j}_{1}\right)\right\}\right\},\]as claimed. \(\blacksquare\) (b) Consider the function \[x\left(\text{i}\right) := \frac{1}{2}\left(\max_{\text{j}_{0}\colon\text{i}+1}\left\{a\left(\text{j}_{0}\right)\right\}+\min_{\text{j}_{1}\colon\text{n}-\text{i}}\left\{a\left(\text{i}-1+\text{j}_{1}\right)\right\}\right),\]increasing in \(\text{i}\) as both summands are, and remark that \begin{align*}\left|\frac{1}{2}\left(\max_{\text{j}_{0}\colon\text{i}+1}\left\{a\left(\text{j}_{0}\right)\right\}+\min_{\text{j}_{1}\colon\text{n}-\text{i}}\left\{a\left(\text{i}-1+\text{j}_{1}\right)\right\}\right)\ -\ a\left(\text{i}\right)\right|\ &=\ \left|\frac{1}{2}\left(\max_{\text{j}_{0}\colon\text{i}+1}\left\{a\left(\text{j}_{0}\right)\right\}-a\left(\text{i}\right)\right)\ +\ \frac{1}{2}\left(\min_{\text{j}_{1}\colon\text{n}-\text{i}}\left\{a\left(\text{i}-1+\text{j}_{1}\right)\right\}-a\left(\text{i}\right)\right)\right| \\ &=\ \left|\frac{1}{2}\max_{\text{j}_{0}\colon\text{i}+1}\left\{a\left(\text{j}_{0}\right)-a\left(\text{i}\right)\right\}\ -\ \frac{1}{2}\max_{\text{j}_{1}\colon\text{n}-\text{i}}\left\{a\left(\text{i}\right)-a\left(\text{i}-1+\text{j}_{1}\right)\right\}\right|\\ &\leq\ \max\left(\frac{1}{2}\max_{\text{j}_{0}\colon\text{i}+1}\left\{a\left(\text{j}_{0}\right)-a\left(\text{i}\right)\right\},\ \frac{1}{2}\max_{\text{j}_{1}\colon\text{n}-\text{i}}\left\{a\left(\text{i}\right)-a\left(\text{i}-1+\text{j}_{1}\right)\right\}\right)\\ &\leq\ \frac{1}{2}\max_{\substack{\text{j}_{0}\colon\text{n},\ \text{j}_{1}\colon\text{n} \\ \text{j}_{0}\ \leq\ \text{j}_{1}}}\left\{a\left(j_{0}\right)-a\left(j_{1}\right)\right\}\\ &=\ \frac{1}{2}\max_{\text{i}\colon\text{n}}\left\{\max_{\text{j}_{0}\colon\text{i}+1}\left\{a\left(\text{j}_{0}\right)\right\}-\min_{\text{j}_{1}\colon\text{n}-\text{i}}\left\{a\left(\text{i}-1+\text{j}_{1}\right)\right\}\right\}\end{align*}Whence in conjunction with (a) the claimed equality. \(\blacksquare\)

(a) In case $a_1\leq a_2\leq \dots \leq a_n$ we have $\max |x_i-a_i|\geq 0\geq \frac d2$. Otherwise, let $d=a_k-a_l>0$ for $k<l.$ Then $$\max |x_i-a_i|\geq \frac{|a_k-x_k|+|x_l-a_l|}{2}\geq \frac{|a_k-a_l+x_l-x_k|}{2}= \frac{a_k-a_l+x_l-x_k}{2}\geq \frac d2 \quad \blacksquare$$ (b) We claim that the sequence $x_k=\max_{1\leq i\leq k} a_i-\frac d2$ satisfies. For an arbitrary fixed $i$ let $x_i=a_j-\frac d2.$ Then $$0\leq a_j-a_i\leq d\implies |x_j-a_i|=|a_j-a_i-\frac d2|\leq \frac d2.$$By the part (a) the equality must occur, as required.

The key part of the problem is the following characterization of $d$. Claim: $d=\max_{i<j}(a_i-a_j)$. Proof: Clear. With this in mind, part (a) follows by the triangle inequality, since for $i>j$ with $a_i-a_j$ maximal we have $$d=a_i-a_j=(a_i-x_i)+(x_i-a_j)\leq (a_i-x_i)+(x_j-a_j)=|x_i-a_i|+|x_j-a_j|$$and the conclusion is clear. Motivated by this, for part (b) we select $x_k=\max_{i\leq k} a_i-\frac{d}{2}$ which clearly works: \begin{align*} a_k-x_k&\leq \max_{i \leq k} a_i-x_k=\frac{d}{2}\\ x_k-a_k&\leq \max_{i \leq k} a_i-\frac{d}{2}-\left(\max_{i\leq k} a_i-d\right)=\frac{d}{2}.~\blacksquare \end{align*}

It is easy to see $d = \max_{1\leq i\leq j \leq n} (a_i-a_j)$. Consider the pair $(i,j)$ that achieves this maximum. One of $|x_i - a_i|$ and $|x_j-a_j|$ is at least $\frac d2$, which proves part a. For part b, set $x_i = \max_{1\leq j \leq i}(a_i) - \frac d2$.

This could easily show up in a coding contest in a format such as: Given an array $A$ of $n$ numbers $a_1, a_2, a_3 \dots$, find an array $X$ of $n$ numbers $x_1 \leq x_2 \leq x_3 \dots x_n$ such that $\max_{1\leq i \leq n}|x_i - a_i|$ is minimized. "Binary searching on the answer" would allow one to motivate the following ideas/constructions: Sketch of Proof: a. We show by way of contradiction that it is not possible for there to exist $x_1 \leq x_2 \leq \dots x_n$ such that $a_i - \frac{d}{2} < x_i < a_i + \frac{d}{2} $ for $i = 1, 2, \dots n$. Now if there exist $j \leq k$ such that $a_j - \frac{d}{2} \geq a_k + \frac{d}{2} \implies a_j - a_k \geq d$, then this construction is infeasible. But by definition of how $d$ is defined, there will exist $j, k$ that satisfy this. This creates a contradiction. b. Consider $x_i = \max(a_1 -\frac{d}{2}, a_2 - \frac{d}{2} \dots a_i - \frac{d}{2})$. Clearly $x_t \leq x_{t+1}$ and $a_t - \frac{d}{2} \leq x_t$. Now it suffices to show that $a_k - \frac{d}{2} \leq a_t + \frac{d}{2}$ for $k \leq t$. We merely need that $a_k - a_t \leq \frac{d}{2}$ which is true due to how $d$ is defined.

Can someone tell me if my construction works or not please?

Let $d = a_p - a_q$ where $ p< q$. Now, if $x_p \ge a_p$, we have $x_q \ge x_p \ge a_q +d $, so we're done, if $x_p + \frac d2 \le a_p$, we are done, if $a_p - \frac d2 \le x_p \le a_p$, we know that $x_q \ge x_p \ge a_p - \frac d2 = a_q + \frac d2$, so we're done. All cases are exhausted. Now we find an equality case. We use induction. The base cases of $n = 1,2$, obviously holds. Now put $x_i = \frac{a_p + a_q}{2}$ for $p \le i \le q$, this clearly works, since if there was some $x_i$ with $x_i - a_i > \frac d2$, we would have $a_i < a_q$, impossible, likewise if we had $a_i - x_i > \frac d2$ we would have $a_i > a_p$, impossible. Keep assigning $x_i = x_p$ for $i < p$, decrementing $i$ until we get some $a_i$ satisfying $a_i$ < $a_q$ (or just end up labeling all the $x_i$). Now it suffices to use the inductive hypothesis on the sequence formed by $a_1 \cdots a_i$. Clearly since the $d$ for the subsequence, labeled $d_p$ is guaranteed to be smaller, so $x_i < a_i + d_p < a_q + d = x_{p} = x_{i + 1}$. Thus the nondecreasing condition is satisfied, and so is the inequality. We can do the symmetrical thing on the other side, done.

In the case where the $a_i$ are non-strictly increasing, the absolute values are always greater than $0,$ and set $x_i = a_i$ to get equality. Now, notice that $d$ is the largest value of the difference $a_i - a_j$ over all $i \le j.$ We may assume $i < j$ here since $i = j$ gives the case above. Let $i = p, j = q$ be the equality case. We claim that at least one of $|x_p - a_p|$ and $|x_q - a_q|$ is at least $\frac{d}{2},$ which finishes. By the Triangle Inequality, $$|a_p - x_p| + |a_q - x_q| \ge |a_p - a_q + x_q - x_p| \ge |a_p - a_q| = a_p - a_q = d$$since $d \ge 0$ (it is at least $a_1 - a_1 = 0$) and $x_q - x_p \ge 0$ (we are given that the $x_i$ are increasing, and $p < q$). Therefore, by Pigeonhole, at least one of the two quantities is at least $\frac{d}{2},$ as desired. For the equality case, take $x_i = \max(a_1, \dots, a_n) - \frac{d}{2}$ for all $i.$ It is not hard to verify this works.

(a) For the sake of a contradiction, assume otherwise. Then for all $1 \leq i \leq n$ we have that $$|x_i-a_i| < \frac{d}{2}.$$Also, note that the definition of $d$ is equivalent to $d := \max \{a_i-a_j \, | \, 1 \leq i \leq j \leq n \}.$ Now, suppose that $d=a_i-a_j$ yields the maximum, then $i \leq j,$ while clearly $a_i \geq a_j$ since otherwise $d < 0,$ a contradiction. Then place the points $a_i, a_j$ on the number line, and for each of these points map out the possible places for where $x_i, x_j$ can go. (meaning $\left \{ x \, | \, |x-a_k| \leq \frac{d}{2} \right \}$ for $k=i, j$) It is easy to see that these regions do not intersect, therefore $x_i > x_j,$ a contradiction. QED (b) Note that $x_i = \max \{ a_1, a_2, \cdots, a_n\}-\frac{d}{2}$ works by inspection.

The example from $n = 2$ provided inspiration. Let $d = a_m - a_n$ with $m \le n$, then \[ \max \{ |x_i - a_i| : 1 \le i \le n \} \ge \max \{ |x_m - a_m|, |x_n - a_n| \}. \]Therefore, we have reduced to the situation where $n = 2$. For part (b), we just need to put $x_i = a_m - \frac{d}{2}$ for all $1 \le i \le n$.

For each $i$ let $d=a_i-a_j$ also scale all of $a_1$, $a_2$, \dots, $a_n$ so that they are positive reals also suppose that $d$ is positive as if it is negative the result is immediate. Now from triangle inequality: \[\vert a_i-x_i \vert+ \vert a_j-x_j \vert \geq \vert a_i-a_j-x_i+x_j \vert\]as $x_i\leq x_j$, and $a_i-a_j$ is positive this means: \[\vert a_i-a_j-x_i+x_j \vert \geq \vert a_i-a_j \vert = d\]Thus as: \[\vert a_i-x_i \vert+ \vert a_j-x_j \vert \geq d \]One of the two expressions must be $\geq \frac{d}{2}$. For part $b$ let all the $x_k$ be equal to $\frac{a_i+a_j}{2}$ which clearly works.