Let $0<x_1<x_2<\ldots<x_N<1$ be $N$ points of $[0,1]$. I was reading something in which it says that the following two expressions are clearly equal:
$$\max_{1\leq i\leq N}\max\left(\left|\frac{i}{N}-x_i\right|,\left|\frac{i-1}{N}-x_i\right|\right)=\frac{1}{2N}+\max_{1\leq i\leq N}\left|x_i-\frac{2i-1}{2N}\right|.$$
I can prove it tediously by going through all cases of "What if this is the maximal element...", but I don't see why it is clear?
Also, what is really going on here? Somehow we manage to reduce the $2N$ elements in the maximum on the left hand side to just $N$ elements on the right hand side. There must be a special structure to this problem that lets us do this.
Instead of looking at $$\max_{1\leq i\leq N}\max\left(\left|\frac{i}{N}-x_i\right|,\left|\frac{i-1}{N}-x_i\right|\right)$$ We look at $$\max_{1\leq i\leq N}\max\left(\left|\frac{i}{N}-x_i\right|-\frac{1}{2N},\left|\frac{i-1}{N}-x_i\right|-\frac{1}{2N}\right)$$
Case 1. If $x_i \ge \frac{2i-1}{2N}$
In this case, we note that $|\frac{i-1}{N}-x_i| \ge |\frac{i}{N}-x_i|$.
Therefore, we have $\max \left(\left|\frac{i}{N}-x_i\right|-\frac{1}{2N},\left|\frac{i-1}{N}-x_i\right|-\frac{1}{2N}\right)=|\frac{i-1}{N}-x_i|-\frac{1}{2N}=|x_i-\frac{2i-1}{2N}|$
Case 2. If $x_i \le \frac{2i-1}{2N}$
This case is handled similarly.
We note that $|\frac{i}{N}-x_i| \ge |\frac{i-1}{N}-x_i|$.
Therefore, we have $\max \left(\left|\frac{i}{N}-x_i\right|-\frac{1}{2N},\left|\frac{i-1}{N}-x_i\right|-\frac{1}{2N}\right)=|\frac{i}{N}-x_i|-\frac{1}{2N}=|x_i-\frac{2i-1}{2N}|$
Now the result follows! We are done. $\blacksquare$