Rearrangement Inequality. Chebyshev’s Inequality

If \( x_1 \), \( x_2 \), \( \dots \), \( x_n \) and \( y_1 \), \( y_2 \), \( \dots \), \( y_n \) are two non-decreasing sequences of real numbers, and if \( \sigma_1 \), \( \sigma_2 \), \( \dots \), \( \sigma_n \) is any permutation of \( \{1,2,\dots, n\} \), then the following inequality holds: \[ x_1y_n+x_2y_{n-1}+\cdots+x_ny_1\leq x_1y_{\sigma_1}+x_2y_{\sigma_2}+\cdots+ x_ny_{\sigma_n}\leq x_1y_1+x_2y_2+\cdots+x_ny_n.\]

Let us prove the right inequality. The left one will follow by applying the right one to the sequences \( x_1 \), \( x_2 \), \( \dots \), \( x_n \) and \( -y_n \), \( -y_{n-1} \), \( \dots \), \( -y_1 \).

We will prove the right inequality by induction on \( n \). For \( n=2 \), the statement can be easily proved. Assume that the statement holds for all pairs of sequences of lengths \( 1 \), \( 2 \), \( \dots \), \( n \). Let \( x_1\leq \) \( x_2\leq \) \( \cdots\leq \) \( x_{n+1} \) and \( y_1\leq \) \( y_2\leq \) \( \cdots\leq \) \( y_{n+1} \) be two sequences of real numbers, and let \( \sigma_1 \), \( \sigma_2 \), \( \dots \), \( \sigma_{n+1} \) be a permutation of \( \{1,2,\dots, n+1\} \). Let \( i \) be the integer such that \( \sigma_i=n+1 \).

Then we have \[ x_1y_{\sigma_1}+x_2y_{\sigma_2}+\cdots+\left(x_iy_{\sigma_i}+x_{i+1}y_{\sigma_{i+1}}\right)+\cdots+x_{n+1}y_{n+1} \leq x_1y_{\sigma_1}+x_2y_{\sigma_2}+\cdots+ \left(x_iy_{\sigma_{i+1}}+x_{i+1}y_{\sigma_{i}}\right)+\cdots+x_{n+1}y_{n+1}.\] The last inequality holds because we applied the case \( n=2 \) for the non-decreasing sequences \( (x_i, x_{i+1}) \) and \( \left(y_{\sigma_{i+1}},y_{\sigma_{i}}\right) \). The previous inequality can be now written as \[ \sum_{j=1}^{n+1}x_jy_{\sigma_j}\leq\sum_{j=1}^{n+1} x_jy_{\tau^1_j},\] where \( \tau^1_1 \), \( \tau^1_2 \), \( \dots \), \( \tau^1_{n+1} \) is the permutation obtained from \( \sigma_1 \), \( \sigma_2 \), \( \dots \), \( \sigma_{n+1} \) by transposing the term \( n+1 \) with the one that is adjacent and to the right. Repeating this procedure we obtain the inequality \[ \sum_{i=j}^{n+1}x_jy_{\sigma_j}\leq \sum_{j=1}^{n+1}x_jy_{\tau^{n+1-i}_j}.\] We now have \( \tau^{n+1-i}_{n+1}=n+1 \) and we can apply inductional hypothesis to obtain \[ \sum_{j=1}^{n}x_jy_{\tau^{n+1-i}_j}\leq\sum_{j=1}^n x_jy_j\quad\Rightarrow\quad \sum_{j=1}^{n+1}x_jy_{\tau^{n+1-i}_j}\leq \sum_{n=1}^{n+1}x_jy_j.\]

If \( a \), \( b \), \( c \), and \( d \) are positive real numbers prove that \[ a^4+b^4+c^4+d^4\geq 4abcd.\]

Assume that \( a\leq b\leq c\leq d \). Applying the rearrangement to the sequences \( (c,d) \) and \( (c^3,d^3) \) we obtain \[ dc^3+cd^3\leq c^4+d^4.\] Applying the same inequality to the sequences \( (b,d) \) and \( (b^3,cd^2) \) we obtain \( db^3+bcd^2\leq b^4+cd^3 \). Together with the previous inequality we have \[ db^3+dc^3+bcd^2\leq b^4+c^4+d^4.\] We now apply the rearrangement inequality to the sequences \( (a,d) \) and \( (a^3,bcd) \) to obtain \( da^3+abcd\leq a^4+bcd^2 \) which together with the previous inequality implies \[ da^3+db^3+dc^3+abcd\leq a^4+b^4+c^4+d^4.\] It suffices to prove that \( 3abcd\leq da^3+db^3+dc^4 \) which is equivalent to \( 3abc\leq a^3+b^3+c^3 \). For this we use the same argument as before.

Let \( a_1\geq a_2\geq\cdots\geq a_n \) and \( b_1\geq b_2\geq\cdots\geq b_n \) be real numbers. Then \begin{eqnarray*} n\sum_{i=1}^n a_ib_i\geq\left(\sum_{i=1}^n a_i \right)\left(\sum_{i=1}^n b_i\right)\geq n\sum_{i=1}^n a_ib_{n+1-i}.\quad\quad\quad\quad\quad (1) \end{eqnarray*} The two inequalities become equalities at the same time when \( a_1=a_2=\cdots=a_n \) or \( b_1=b_2=\cdots=b_n \).

According to rearrangement inequality we have the following relations: \begin{eqnarray*} a_1b_1+a_2b_2+a_3b_3+\cdots+a_nb_n&\geq&a_1b_1+a_2b_2+a_3b_3+\cdots+a_nb_n \geq a_1b_n+a_2b_{n-1}+\cdots +a_nb_1 \\ a_1b_1+a_2b_2+a_3b_3+\cdots+a_nb_n&\geq&a_1b_2+a_2b_3+a_3b_4+\cdots+a_nb_1\geq a_1b_n+a_2b_{n-1}+\cdots +a_nb_1\\ a_1b_1+a_2b_2+a_3b_3+\cdots+a_nb_n&\geq&a_1b_3+a_2b_4+a_3b_5+\cdots+a_nb_2\geq a_1b_n+a_2b_{n-1}+\cdots +a_nb_1\\ &&\vdots\\ a_1b_1+a_2b_2+a_3b_3+\cdots+a_nb_n&\geq&a_1b_n+a_2b_1+a_3b_2+\cdots+a_nb_{n-1}\geq a_1b_n+a_2b_{n-1}+\cdots +a_nb_1. \end{eqnarray*} Summing up these \( n \) inequalities we obtain (1).

Let \( a_1\geq a_2\geq\cdots\geq a_n \) and \( b_1\geq b_2\geq\cdots\geq b_n \) be any real numbers, and \( m_1,\dots, m_n \) non-negative real numbers whose sum is \( 1 \). Then \begin{eqnarray*} \sum_{i=1}^n a_ib_im_i\geq\left(\sum_{i=1}^n a_i m_i\right) \left(\sum_{i=1}^n b_im_i\right).\quad\quad\quad\quad\quad (2) \end{eqnarray*} The inequality become an equality if and only if \( a_1=a_2=\cdots=a_n \) or \( b_1=b_2=\cdots=b_n \).

From \( (a_i-a_j)(b_i-b_j)\geq 0 \) we get: \begin{eqnarray*} \sum_{i,j}(a_i-a_j)(b_i-b_j)m_im_j\geq 0.\quad\quad\quad\quad\quad(3)\end{eqnarray*} Since \( \left(\sum_{i=1}^n a_im_i\right)\cdot \left(\sum_{i=1}^n b_im_i\right)=\sum_{i,j} a_ib_jm_im_j \), (3) implies that \begin{eqnarray*}0&\leq& \sum_{i,j}a_ib_im_im_j-\sum_{i,j} a_ib_jm_im_j-\sum_{i,j}a_jb_im_jm_i + \sum_{i,j}a_jb_j m_im_j\\ &=& 2\left[\sum_i a_ib_im_i- \left(\sum_i a_im_i\right)\left(\sum_i b_im_i\right) \right].\; \end{eqnarray*}

If \( a \), \( b \), and \( c \) are positive real numbers, prove the inequality \[ \frac{ab}{a+b}+\frac{bc}{b+c}+\frac{ca}{c+a}\leq\frac{3(ab+bc+ca)}{2(a+b+c)}.\]

Assume that \( a\leq b\leq c \). Then we have \( a+b\geq a+c\geq c+a \). We also have \( \frac1a\leq \frac1b\leq \frac1c \) implying \( \frac1a+\frac1b\leq\frac1a+\frac1c\leq\frac1b+\frac1c \) and \[ \frac1{\frac1a+\frac1b}\geq \frac1{\frac1a+\frac1c}\geq \frac1{\frac1b+\frac1c}.\] The last three inequalities can be rewritten as \[ \frac{ab}{a+b}\geq\frac{ac}{a+c}\geq\frac{bc}{b+c}.\] Chebyshev’s inequality now implies \[ 3\cdot \left((a+b)\cdot \frac{ab}{a+b}+(a+c)\cdot \frac{ac}{a+c}+(b+c)\frac{bc}{b+c}\right)\geq \left((a+b)+(a+c)+(b+c)\right)\cdot \left(\frac{ab}{a+b}+\frac{ac}{a+c}+\frac{bc}{b+c}\right).\] The last inequality is equivalent to the required one. The eqeuality holds if and only if \( a=b=c \).

Prove that the sum of distances of the orthocenter from the sides of an acute triangle is less than or equal to \( 3r \), where the \( r \) is the inradius.

Denote \( a=BC \), \( b=CA \), \( c=AB \) and let \( S_{ABC} \) denote the area of the triangle \( ABC \). Let \( d_A \), \( d_B \), \( d_C \) be the distances from \( H \) to \( BC \), \( CA \), \( AB \), and \( A^{\prime} \), \( B^{\prime} \), \( C^{\prime} \) the feet of perpendiculars from \( A \), \( B \), \( C \). Then we have \( ad_a+bd_b+cd_c=2(S_{BCH}+S_{ACH}+S_{ABH})=2P \). On the other hand if we assume that \( a\geq b\geq c \), it is easy to prove that \( d_A\geq d_B\geq d_C \). Indeed, \( a\geq b \) implies \( \angle A\geq \angle B \) hence \( \angle HCB^{\prime} \leq \angle HCA^{\prime} \) and \( HB^{\prime}\leq HA^{\prime} \). The Chebyshev’s inequality implies \[ (a+b+c)r=2P=ad_a+bd_b+cd_c\geq\frac13(a+b+c)(d_a+d_b+d_c). \]

If \( a, b \), and \( c \) are the lengths of the sides of a triangle, \( s \) its semiperimeter, and \( n\geq 1 \) an integer, prove that \[ \frac{a^n}{b+c}+\frac{b^n}{c+a}+ \frac{c^n}{a+b} \geq \left(\frac23\right)^{n-2} \cdot s^{n-1}.\]

Applying the Chebyshev’s inequality first we get \[ \frac{a^n}{b+c}+\frac{b^n}{c+a}+ \frac{c^n}{a+b} \geq \frac{a^n+b^n+c^n}3\cdot \left(\frac1{a+b}+\frac1{b+c} + \frac1{c+a}\right).\] The Cauchy-Schwartz inequality gives: \[ 2(a+b+c)\left(\frac1{a+b} + \frac1{b+c}+\frac1{c+a}\right) \geq 9,\] and the inequality \( M_n\geq M_2 \) gives \[ \frac{a^n+b^n+c^n}3 \geq \left(\frac{a+b+c}3\right)^n.\] In summary \begin{eqnarray*} \frac{a^n}{b+c}+\frac{b^n}{c+a}+ \frac{c^n}{a+b}&\geq & \left(\frac{a+b+c}3\right)^n\left(\frac1{a+b} + \frac1{b+c} + \frac1{c+a}\right)\\ & \geq & \frac13\cdot\frac12\cdot \left(\frac23s\right)^{n-1}\cdot 9 = \left(\frac23\right)^{n-2}s^{n-1}. \end{eqnarray*}

Let \( 0< x_1 \leq x_2 \leq \cdots \leq x_n \) (\( n\geq 2 \)) and \[ \frac1{1+x_1} + \frac1{1+x_2}+ \cdots + \frac1{1+x_n} = 1.\] Prove that \[ \sqrt{x_1} + \sqrt{x_2} + \cdots + \sqrt{x_n} \geq (n-1) \left( \frac1{\sqrt{x_1}}+ \frac1{\sqrt{x_2}} + \cdots + \frac1{\sqrt{x_n}}\right).\]

It is enough to prove that \begin{eqnarray}\nonumber && \left(\sqrt{x_1}+\frac1{\sqrt{x_1}}\right) + \left(\sqrt{x_2}+\frac1{\sqrt{x_2}}\right)+ \cdots + \left(\sqrt{x_n}+\frac1{\sqrt{x_n}}\right)\\ \nonumber & \geq & n\left( \frac1{\sqrt{x_1}}+ \frac1{\sqrt{x_2}} + \cdots + \frac1{\sqrt{x_n}}\right),\end{eqnarray} or equivalently \begin{eqnarray}\nonumber && \left(\frac{1+x_1}{\sqrt{x_1}} + \cdots + \frac{1+x_n}{\sqrt{x_n}}\right) \left(\frac1{1+x_1} + \frac1{1+x_2}+ \cdots + \frac1{1+x_n}\right)\\ \nonumber & \geq &n\cdot \left(\frac1{\sqrt{x_1}}+ \frac1{\sqrt{x_2}} + \cdots + \frac1{\sqrt{x_n}}\right).\end{eqnarray} Consider the function \( f(x)=\sqrt x + \frac{1}{\sqrt{x}} = \frac{x+1}{\sqrt x}, x\in (0,+ \infty) \). It is easy to verify that \( f \) is non-decreasing on \( (1, + \infty) \) and that \( f(x)=f\left(\frac1x\right) \) for every \( x> 0 \). Furthermore from the given conditions it follows that only \( x_1 \) can be less than \( 1 \) and that \( \frac1{1+x_2} \leq 1- \frac1{1+x_1} = \frac{x_1}{1+x_1} \). Hence \( x_2\geq \frac1{x_1} \). Now it is clear that (in both of the cases \( x_1 \geq 1 \) and \( x_1< 1 \)): \[ f(x_1)=f\left(\frac1{x_1}\right) \leq f(x_1)\leq \cdots \leq f(x_n).\] This means that the sequence \( \left(\frac{1+x_k}{x_k}\right)_{k=1}^n \) is non-decreasing. Thus according to the Chebyshev’s inequality we have: \begin{eqnarray}&&\nonumber \left(\frac{1+x_1}{\sqrt{x_1}} + \cdots + \frac{1+x_n}{\sqrt{x_n}}\right) \left(\frac1{1+x_1} + \frac1{1+x_2}+ \cdots + \frac1{1+x_n}\right)\\ \nonumber &\geq& n\cdot \left(\frac1{\sqrt{x_1}}+ \frac1{\sqrt{x_2}} + \cdots + \frac1{\sqrt{x_n}}\right). \end{eqnarray} The equality holds if and only if \( \frac{1}{1+x_1} = \cdots = \frac1{1+x_n} \), or \( \frac{1+x_1}{\sqrt{x_1}}=\cdots = \frac{1+x_n}{\sqrt{x_n}}, \) which implies that \( x_1=x_2 = \cdots = x_n \). Thus the equality holds if and only if \( x_1=\cdots = x_n=n-1 \).