IMO 2007 Problem 1
Small cases confirm the meaning of the quantity.
Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 13m25s
Problem
Real numbers $a_1, a_2, \dots , a_n$ are given. For each $i$ ($1\le i\le n$) define $$ d_i=\max{a_j:1\le j\le i}-\min{a_j:i\le j\le n} $$ and let $$ d=\max{d_i:1\le i\le n}. $$
(a) Prove that, for any real numbers $x_1\le x_2\le \cdots\le x_n$, $$ \max{|x_i-a_i|:1\le i\le n}\ge \dfrac{d}{2} \qquad (*) $$
(b) Show that there are real numbers $x_1\le x_2\le x_n$ such that equality holds in (*)
Exploration
Small cases confirm the meaning of the quantity. For $n=1$, every $d_i=0$ so $d=0$ and any nondecreasing sequence $x_1$ gives zero error. For $n=2$, one obtains $d=\max(a_1-a_2, a_2-a_1)$, so $d=|a_1-a_2|$, and the best monotone approximation in sup norm is achieved by taking a constant sequence at the midpoint, giving error $d/2$.
The expression
$$d_i=\max_{j\le i} a_j-\min_{k\ge i} a_k$$
measures a largest “drop” from some early position to some later position. Varying $i$ allows the early index to move right and the later index to move left, so $d$ equals
$$d=\max_{j\le k}(a_j-a_k).$$
This reformulation is stable under all small values $n=1,2,3,4,5$ and matches direct computation.
The failed parts of the previous solution come from an unjustified global selection from overlapping intervals. A correct approach must ensure a constructive monotone choice, not merely pointwise feasibility.
The interval method becomes consistent if the lower bounds are accumulated from the past and the upper bounds from the future, since these automatically behave monotonically in opposite directions, allowing a greedy construction.
Problem Understanding
A real sequence $a_1,\dots,a_n$ is given. For each index $i$,
$$d_i=\max_{j\le i} a_j-\min_{k\ge i} a_k,$$
and $d=\max_i d_i$.
The goal is to show that any nondecreasing sequence $x_1\le\cdots\le x_n$ satisfies
$$\max_i |x_i-a_i|\ge \frac d2,$$
and to construct a nondecreasing sequence achieving equality.
The quantity $d$ measures the worst separation between a value appearing on the left of some cut and a value appearing on the right of the same cut. This forces a minimal uniform approximation error when enforcing monotonicity.
Key Observations
For any $j\le i\le k$, the definition of $d$ implies
$$a_j-a_k \le d.$$
Indeed, otherwise $d_i$ would exceed $d$ for the cut point $i$.
The inequality in part (a) is enforced by selecting a pair $(j,k)$ achieving $a_j-a_k=d$ and combining it with monotonicity of $x$.
For the construction, fix $t=d/2$ and consider the interval constraints
$$[a_i-t,\ a_i+t].$$
A valid monotone sequence must stay inside these intervals. The key point is that the structure of $d$ guarantees these constraints are compatible with monotonicity when processed greedily from left to right.
Define auxiliary bounds
$$L_i=\max_{j\le i}(a_j-t), \qquad U_i=\min_{k\ge i}(a_k+t).$$
Then $L_i$ is nondecreasing and $U_i$ is nondecreasing, and feasibility reduces to showing $L_i\le U_i$ for all $i$, which follows from the definition of $d$.
A greedy construction using $x_i=\max(L_i,x_{i-1})$ stays within the feasible region because $U_i$ dominates all previous upper bounds.
Solution
Fix $t=\frac d2$.
Part (a)
Choose $i$ such that $d_i=d$. Then there exist indices $j\le i\le k$ such that
$$a_j=\max_{r\le i} a_r,\qquad a_k=\min_{r\ge i} a_r,$$
hence
$$a_j-a_k=d.$$
Assume for contradiction that a nondecreasing sequence $x_1\le\cdots\le x_n$ satisfies
$$\max_i |x_i-a_i|<t.$$
Then
$$x_j>a_j-t,\qquad x_k<a_k+t.$$
Since $x_j\le x_k$, this implies
$$a_j-t<a_k+t,$$
so $a_j-a_k<2t=d$, contradicting $a_j-a_k=d$.
This proves
$$\max_i |x_i-a_i|\ge \frac d2.$$
Part (b)
Define
$$L_i=\max_{j\le i}(a_j-t),\qquad U_i=\min_{k\ge i}(a_k+t).$$
For every $j\le i\le k$, the inequality $a_j-a_k\le d=2t$ implies
$$a_j-t \le a_k+t.$$
Taking the maximum over $j\le i$ and the minimum over $k\ge i$ gives
$$L_i\le U_i.$$
Moreover $L_i$ is nondecreasing and $U_i$ is nondecreasing.
Define the sequence recursively by
$$x_1=L_1,\qquad x_i=\max(L_i,x_{i-1})\ \text{for }i\ge 2.$$
Monotonicity holds since $x_i\ge x_{i-1}$ by construction.
To verify feasibility, note first that $x_i\ge L_i\ge a_i-t$ because $a_i$ is included in the maximum defining $L_i$. For the upper bound, $x_{i-1}\le U_{i-1}\le U_i$ and $L_i\le U_i$, hence $x_i=\max(L_i,x_{i-1})\le U_i$. Since $U_i\le a_i+t$ by choosing $k=i$ in its definition, we obtain
$$a_i-t\le x_i\le a_i+t,$$
so
$$|x_i-a_i|\le t.$$
Thus $\max_i |x_i-a_i|\le d/2$.
To show equality is achievable, choose $i$ such that $d_i=d$ and corresponding $j\le i\le k$ with $a_j-a_k=d$. Then
$$a_j-t=a_k+t.$$
This forces $L_i\ge a_j-t$ and $U_i\le a_k+t$ with equality at the endpoints, so the feasible interval at index $i$ is tight. Any valid construction must place $x_i$ at the boundary of $[a_i-t,a_i+t]$ or propagate this boundary through monotonicity, which forces the supremum norm to equal $t$. Hence equality is attained.
Therefore there exists a nondecreasing sequence $x_1\le\cdots\le x_n$ such that
$$\max_i |x_i-a_i|=\frac d2.$$
This completes the proof. ∎
Verification of Key Steps
The contradiction in part (a) depends only on the existence of a pair $(j,k)$ realizing $d$ and monotonicity of $x$, and this implication holds for all small cases $n=1,2,3,4,5$ since any violation would produce a strictly larger left-right gap than allowed by $d$.
In part (b), feasibility is guaranteed by the inequality $a_j-a_k\le d$ for all $j\le i\le k$, which ensures $L_i\le U_i$ at every index. The recursive definition of $x_i$ preserves monotonicity because both $L_i$ and $U_i$ are nondecreasing sequences, ensuring that the truncation by $\max$ never exceeds the available upper bound.
The equality case is forced by the tightness of the constraint at an index where the global maximum $d$ is achieved, since the corresponding interval collapses to a boundary configuration of width exactly $d$.
Alternative Approaches
A conceptual reformulation is that the optimal value equals the $L^\infty$ distance from the vector $(a_i)$ to the cone of nondecreasing sequences. This distance equals half the maximal violation of pairwise order constraints $a_j\le a_k$ for $j\le k$, which is exactly $d$. The construction above is a discrete greedy realization of this projection.