Problem 4002 from Crux Mathematicorum


Problem 4002 from Crux Mathematicorum

Solution 1

We can prove the above statement by proving its simplified form, for $n=2:$

Let $x_1\lt x_2\,$ and $y_1\lt y_2\,$ be numbers such that $x_i+y_j$ is always in $I.\,$ Then

$\displaystyle f(x_1+y_1)+f(x_2+y_2)\ge f(x_1+y_2)+f(x_2+y_1).$

The reason why this suffices: if we choose a permutation $z_1,z_2,\ldots,z_n\,$ such that $z_i\gt z_j\,$ for some $i\lt j,\,$ then we will have

$\displaystyle f(x_i+z_i)+f(x_j+z_j)\ge f(x_i+z_j)+f(x_j+z_i).$

We would then be able to interchange $z_i$ and $z_j$ without decreasing the overall sum. Thus a permutation $z_1,z_2,\ldots,z_n\,$ that gives the largest overall sum is where $z_i\le z_j\,$ whenever $i\lt j;\,$ i.e., $z_i=y_i$ for all $i.$ Similarly, a permutation $z_1, z_2, \ldots,z_n$ that gives us the smallest overall sum is one where $z_i \ge z_j$ whenever $i \lt j;$ that is, $z_i = y_{n-i+1}\,$ for all $i.$

Now, to prove the simplified form, observe that, by the definition of convexity, for all $a,b\in I\,$ and for all $t\in[0,1],$ we have

$f(ta+(1-t)b)\le tf(a)+(1-t)f(b).$

Let $a=x_1+y_1$ and $b=x_2+y_2.\,$ Then $a\lt x_1+y_2\lt b,\,$ so for some $t\in [0,1].\,$ we have $x_1+y_2=ta+(1-t)b.\,$ From that, we have

$\begin{align} x_2+y_1&=(x_1+y_1+x_2+y_2)-(x_1+y_2)\\ &=(a+b)-(ta+(1-t)b)\\ &=(1-t)a+tb. \end{align}$


$\begin{align} f(x_1+y_2)+f(x_2+y_1)&=f(ta+(1-t)b)+f((1-t)a+tb)\\ &\le (tf(a)+(1-t)f(b))+((1-t)f(a)+tf(b))\\ &=f(a)+f(b)\\ &=f(x_1+y_1)+f(x_2+y_2), \end{align}$

completing the proof of the simplified claim.

Solution 2

Let $a_k=x_{n-k+1}+y_{n-k+1}\,$ and $b_k=x_{n-k+1}+z_{n-k+1},\,$ $k=1,2,\ldots,n.\,$ Obviously, $b_1\ge b_2\ge\ldots\ge b_n,\,$ because $a_1\ge a_2\ge\ldots\ge a_n\,$ and

$\begin{align} &a_1\ge b_1\\ &a_1+a_2\ge b_1+b_2\\ &a_1+a_2+a_3\ge b_1+b_2+b_3\\ &\ldots\ldots\ldots\\ &a_1+a_2+a_3+\ldots+a_{n-1}\ge b_1+b_2+b_3+\ldots+b_{n-1}\\ &a_1+a_2+a_3+\ldots+a_n= b_1+b_2+b_3+\ldots+b_n.\\ \end{align}$

Then, the required result is a direct consequence of the Hardy-Littlewood-Polya inequality (more accurately, Karamata's inequality.)

Note that taking $f(t)=-\ln t,\,t\gt 0,\,$ we shall obtain Daniel Liu's Reverse Rearrangement Inequality


Solution 3

Since $x_1\leq x_2 \leq \ldots x_n $ and $y_1 \leq y_2 \leq \dots y_n$, and $f$ is convex on all combinations involved, we have, for $n=2$, since $x_1+y_1 \leq x_2+y_2$ but this does not apply to other permutations, here $(x_1+y_2)$ and $(x_2 +y_1)$:

$f(x_1+y_1)+f(x_2+y_2)\geq f(x_1+y_2)+ f(x_2+y_1) $

Proof: Let $x_2= x_1+\epsilon ,y_2=y_1+ \xi $, $\epsilon, \xi \geq0$,

$rhs=f\left(x_1+y_1+\xi\right)+f\left(x_1+y_1+\epsilon \right)$

$lhs=f\left(x_1+y_1+\xi+\epsilon \right)+f\left(x_1+y_1\right)$

by a convexity argument, for all values of $x$ and $x+\xi+\epsilon$ in $I$ (the range in which $f$ is convex). We can dig the argument as follows.

Expanding the rhs for both $\epsilon$ and $\xi$:

$\frac{1}{2} \xi ^2 f''\left(x_1+y_1\right)+\frac{1}{2} \epsilon ^2 f''\left(x_1+y_1\right)+\xi f'\left(x_1+y_1\right)+\epsilon f'\left(x_1+y_1\right)+2 f\left(x_1+y_1\right)$$ Expanding the lhs:

$\frac{1}{2} (\xi +\epsilon )^2 f''\left(x_1+y_1\right)+(\xi +\epsilon ) f'\left(x_1+y_1\right)+2 f\left(x_1+y_1\right)$

The difference $lhs -rhs$ becomes

$lhs -rhs =\xi \epsilon f''\left(x_1+y_1\right) \geq 0$

More generally, for $j\gt i$ and $x_j \geq x_i$:

$f(x_i+y_i)+f(x_j+y_j) \geq f(x_j+y_i)+f(x_i+y_j).$

The rhs corresponds to the second inequality. Combining the maximum and the minimum gives the lowest value.

More generally, if, for $\sigma_i \gt \sigma_j$ , $x_{\sigma_i} \geq x_{\sigma_j}:$

$f(x_{\max{\sigma}}+y_{\min{\sigma}})+f(x_{\max{\sigma}-1}+y_{\min{\sigma}+1}), \ldots$

More generally, for $k> j>i$ and $x_k \geq x_j \geq x_i$:

$f(x_i+y_i)+f(x_j+y_j) \geq f(x_j+y_i)+f(x_i+y_j).$

As to the second inequality, we can show that the $\sum f(.)$ of the diagonal is the smallest of all tuples selecting one line and one column from the square matrix:

$\underline{(x_1+y_n)}\geq (x_1 +y_{n-1})\geq\ldots \geq(x_1+y_1)$

$(x_2+y_n)\geq \underline{(x_2 +y_{n-1})}\geq\ldots \geq(x_2+y_1)$


$(x_n+y_n)\geq (x_n +y_{n-1})\geq\ldots \geq\underline{(x_n+y_1)}$

The proof is along the lines that the underlined combinations

$f(x_1+y_n)+f(x_2+y_{n-1}) \leq f(x_1+y_{n-1})+f(x_2+y_{n}),$

and perturbating along the diagonal.

Hence $\sum f[diagonal]$ provides the smallest possible value and any randomization of the order will increase the sum.

A nitpicker might say that $f\,$ needs to be in $C^2.$ So there is a discrete version to the argument above.


This is problem 4002 from Crux Mathematicorum, proposed by Henry Aniobi. Marian Dinca has kindly communicated to me the problem, along with the published solution by Joseph DiMuro (Solution 1) and a solution of his own (Solution 2). Solution 3 is by N. N. Taleb.


|Contact| |Front page| |Contents| |Algebra| |Probability|

Copyright © 1996-2018 Alexander Bogomolny