NMO Selection Tests for BMO and IMO

Let $a_k = (2k-1)/(2n)$, $k = 1, \dots, n$. The required maximum is $\sum_{k=1}^n f(a_k)$ and is achieved, for instance, at $x_1 = \dots = x_n = 0$ or at $x_1 = \dots = x_n = 1$.

To show that $\sum_{k=1}^n f(a_k)$ is an upper bound for the sum under consideration subject to the given constraint, fix an $n$-tuple $(x_1, \dots, x_n)$ such that $0 \le x_1 \le \dots \le x_n \le 1$, write $[n] = \{1, \dots, n\}$, define an increasing function $\varphi: [n] \to [n]$ by $\varphi(k) = \max \{j: a_j - 1/(2n) \le x_k\}$, and notice that
$$|x_k - a_k| \le |x_k - a_{\varphi(k)}| + |a_{\varphi(k)} - a_k| \le 1/(2n) + |\varphi(k) - k|/n = a_{|\varphi(k)-k|+1},$$
for $k = 1, \dots, n$.

We shall prove that there exists a permutation $\sigma$ of $[n]$ such that $|\varphi(k) - k| + 1 \le \sigma(k)$ for all $k$, so $a_{|\varphi(k)-k|+1} \le a_{\sigma(k)}$ and the conclusion follows:
$$\sum_{k=1}^{n} f(|x_k - a_k|) \le \sum_{k=1}^{n} f(a_{|\varphi(k)-k|+1}) \le \sum_{k=1}^{n} f(a_{\sigma(k)}) = \sum_{k=1}^{n} f(a_k).$$

We now show by induction on $n$ that, for any increasing function $\psi: [n] \to [n]$, there exists a permutation $\sigma$ of $[n]$ such that $|\psi(k) - k| + 1 \le \sigma(k)$ for all $k$.

The base case, $n=1$, is clear. For the induction step, let $n > 1$ and distinguish two cases.

If $\psi(n) < n$, then the restriction of $\psi$ to $[n-1]$ is an increasing function of $[n-1]$ into itself, so $|\psi(k)-k|+1 \le \sigma(k)$, $k=1, \dots, n-1$, for some permutation $\sigma$ of $[n-1]$. Since $|\psi(n)-n|+1 = n-\psi(n)+1 \le n$, the permutation $\sigma$ extends to a permutation of $[n]$ satisfying the required condition by letting $\sigma(n) = n$.

If $\psi(n) = n$, consider the increasing function $\psi': [n-1] \to [n-1]$ defined by $\psi'(k) = \psi(k)$ if $\psi(k) < n$ and $\psi'(k) = n-1$ if $\psi(k) = n$. By the induction hypothesis, there exists a permutation $\pi$ of $[n-1]$ such that $|\psi'(k) - k| + 1 \le \pi(k)$, $k = 1, \dots, n-1$, so $|\psi(k) - k| + 1 \le |\psi'(k) - k| + 2 \le \pi(k) + 1$, $k = 1, \dots, n-1$. Finally, since $|\psi(n) - n| + 1 = 1$, setting $\sigma(k) = \pi(k) + 1$, $k = 1, \dots, n-1$, and $\sigma(n) = 1$ defines the required permutation.