Резюме. In this paper we consider a really very useful inequality, the so called rearrangement inequality, which has may applications and could be used in proving other inequalities. The paper contains a proof of the rearrangement inequality and several examples of its application.

Ключови думи: equality; inequality; rearrangement inequality; permutation; sequence; corollary; example

AMS Subject classification (2010): 97 F 50

ZDM Subject classifiction (2010): F50, N 50

Theorem 1. Consider two collections of real numbers in increasing order:

\[ a_{1} \leq a_{2} \leq \ldots \leq a_{n} \text { and } b_{1} \leq b_{2} \leq \ldots \leq b_{n} \]

For any permutation (\(a_{1}^{\prime}, a_{2}^{\prime}, \ldots, a_{n}^{\prime}\) ) of ( \(a_{1}, a_{2}, \ldots, a_{n}\) ) , it happens that

(1) \(a_{l} b_{l}+a_{2} b_{2}+\ldots+a_{n} b_{n} \geq a_{l}^{\prime} b_{l}+a_{2}^{\prime} b_{2}+\ldots+a_{n}^{\prime} b_{n} \)

(2) \(\geq a_{n} b_{l}+a_{n-1} b_{2}+\ldots+a_{l} b_{n}.\)

Moreover, the equality in (1) holds true iff \(\left(a_{1}^{\prime}, a_{2}^{\prime}, \ldots, a_{n}^{\prime}\right)=\left(a_{1}, a_{2}, \ldots, a_{n}\right)\) and the equality in (2) holds true iff \(\left(a_{1}^{\prime}, a_{2}^{\prime}, \ldots, a_{n}^{\prime}\right)=\left(a_{n}, a_{n-1}, \ldots, a_{1}\right)\). ( (1) is known to be the rearrangement inequality.

Proof of the rearrangement inequality: Suppose that \(b_{1} \leq b_{2} \leq \ldots \leq b_{n}\). Let

\[ \begin{aligned} & S=a_{1} b_{1}+a_{2} b_{2}+\ldots+a_{r} b_{r}+\ldots+a_{s} b_{s}+\ldots+a_{n} b_{n}, \\ & S^{\prime}=a_{1} b_{1}+a_{2} b_{2}+\ldots+a_{s} b_{r}+\ldots+a_{r} b_{s}+\ldots+a_{n} b_{n} . \end{aligned} \]

The difference between \(S\) and \(S^{\prime}\) is that the coefficients of \(b_{r}\) and \(b_{s}\), where \(r \lt s\), are switched. Hence,

\[ S-S^{\prime}=a_{r} b_{r}+a_{s} b_{s}-a_{s} b_{r}-a_{r} b_{s}=\left(b_{s}-b_{r}\right)\left(a_{s}-a_{r}\right) \]

Thus, we have that \(S \geq S^{\prime}\) iff \(a_{s} \geq a_{r}\). Repeating this process we get as a result that the sum \(S\) is maximal when \(a_{l} \leq a_{2} \leq \ldots \leq a_{n}\).

Corollary 1. For any permutation \(\left(a_{1}^{\prime}, a_{2}^{\prime}, \ldots, a_{n}^{\prime}\right)\) of \(\left(a_{1}, a_{2}, \ldots, a_{n}\right)\), we have that \[ a_{1}^{2}+a_{2}^{2}+\ldots+a_{n}^{2} \geq a_{1} a_{1}^{\prime}+a_{2} a_{2}^{\prime}+\ldots+a_{n} a_{n}^{\prime} \]

Corollary 2. For any permutation \(\left(a_{1}^{\prime}, a_{2}^{\prime}, \ldots, a_{n}^{\prime}\right)\) of \(\left(a_{1}, a_{2}, \ldots, a_{n}\right)\), we have that \[ \tfrac{a_{1}^{\prime}}{a_{1}}+\tfrac{a_{2}^{\prime}}{a_{2}}+\ldots+\tfrac{a_{n}^{\prime}}{a_{n}} \geq n \]

In the sequel we propose several examples of application of the rearrangement inequality.

Example 1. Let \(a, b\) a and \(c\) be positive real numbers. Prove Nesbitt’sbitt's inequality \[ \tfrac{a}{b+c}+\tfrac{b}{c+a}+\tfrac{c}{a+b} \geq \tfrac{3}{2} \]

Solution: Without loss of generality, we may assume that \(a \geq b \geq c\). Then clearly \[ \tfrac{1}{b+c} \geq \tfrac{1}{c+a} \geq \tfrac{1}{a+b} \]

By the rearrangement inequality we deduce

\[ \tfrac{a}{b+c}+\tfrac{b}{c+a}+\tfrac{c}{a+b} \geq \tfrac{b}{b+c}+\tfrac{c}{c+a}+\tfrac{a}{a+b} \]

and \[ \tfrac{a}{b+c}+\tfrac{b}{c+a}+\tfrac{c}{a+b} \geq \tfrac{c}{b+c}+\tfrac{a}{c+a}+\tfrac{b}{a+b} \] Adding the last two inequalities we obtain that or

\[ \begin{gathered} 2\left(\tfrac{a}{b+c}+\tfrac{b}{c+a}+\tfrac{c}{a+b}\right) \geq 3 \\ \tfrac{a}{b+c}+\tfrac{b}{c+a}+\tfrac{c}{a+b} \geq \tfrac{3}{2}, \text { q.e.d. } \end{gathered} \]

Equality holds true iff \(a=b=c\).

Example 2. (IMO 1978.) Let \(x_{1}, x_{2}, \ldots, x_{n}\) be different positive integers. Prove the inequality

\[ \tfrac{x_{1}}{1^{2}}+\tfrac{x_{2}}{2^{2}}+\ldots+\tfrac{x_{n}}{n^{2}} \geq \tfrac{1}{1}+\tfrac{1}{2}+\ldots+\tfrac{1}{n} \]

Solution: Let \(\left(a_{1}, a_{2}, \ldots, a_{n}\right)\) be a permutation of \(\left(x_{1}, x_{2}, \ldots, x_{n}\right)\) with \(a_{1} \leq a_{2} \leq \ldots \leq a_{n}\) and \(\left(b_{1}, b_{2}, \ldots, b_{n}\right)=\left(\tfrac{1}{n^{2}}, \tfrac{1}{(n-1)^{2}}, \ldots, \tfrac{1}{1^{2}}\right)\), , that is \(b_{i}=\tfrac{1}{(n+1-i)^{2}}\) for \(i=1,2, \ldots, n\).

Consider the permutation (\(a_{1}^{\prime}, a_{2}^{\prime}, \ldots, a_{n}^{\prime}\) ) of ( \(a_{1}, a_{2}, \ldots, a_{n}\) ) defined by \(a_{i}^{\prime}=x_{n+l-i}\), for \(i=1,2, \ldots, n\). Using inequality (2) we may claim that

\[ \begin{gathered} \tfrac{x_{1}}{1^{2}}+\tfrac{x_{2}}{2^{2}}+\ldots+\tfrac{x_{n}}{n^{2}}=a_{1}^{\prime} b_{1}+a_{2}^{\prime} b_{2}+\ldots+a_{n}^{\prime} b_{n} \\ \geq a_{n} b_{1}+a_{n-1} b_{2}+\ldots+a_{1} b_{n} \\ =a_{1} b_{n}+a_{2} b_{n-1}+\ldots+a_{n} b_{1} \\ =\tfrac{a_{1}}{1^{2}}+\tfrac{a_{2}}{2^{2}}+\ldots+\tfrac{a_{n}}{n^{2}} \end{gathered} \]

Since \(1 \leq a_{1}, 2 \leq a_{2}, \ldots, n \leq a_{n}\) we have that

\[ \tfrac{x_{1}}{1^{2}}+\tfrac{x_{2}}{2^{2}}+\ldots+\tfrac{x_{n}}{n^{2}} \geq \tfrac{a_{1}}{1^{2}}+\tfrac{a_{2}}{2^{2}}+\ldots+\tfrac{a_{n}}{n^{2}} \geq \tfrac{1}{1^{2}}+\tfrac{2}{2^{2}}+\ldots+\tfrac{n}{n^{2}}=\tfrac{1}{1}+\tfrac{1}{2}+\ldots+\tfrac{1}{n}, \text { q.e.d. } \]

Equality holds true iff \(x_{1}=1, x_{2}=2, \ldots, x_{n}=n\).

Example 3. Let \(a, b, c\) be positive real numbers. Prove the inequality \[ \tfrac{a^{2}+c^{2}}{b}+\tfrac{b^{2}+a^{2}}{c}+\tfrac{c^{2}+b^{2}}{a} \geq 2(a+b+c) . \]

Solution: Since the given inequality is symmetric, without loss of generality we

may assume that \(a \geq b \geq c\). Then clearly \[ a^{2} \geq b^{2} \geq c^{2} \text { and } \tfrac{1}{c} \geq \tfrac{1}{b} \geq \tfrac{1}{a} \]

By the rearrangement inequality we have

(3) \( \cfrac{a^{2}}{b}+\cfrac{b^{2}}{c}+\cfrac{c^{2}}{a}=a^{2} \cdot \cfrac{1}{b}+b^{2} \cdot \cfrac{1}{c}+c^{2} \cdot \cfrac{1}{a} \geq a^{2} \cdot \cfrac{1}{a}+b^{2} \cdot \cfrac{1}{b}+c^{2} \cdot \cfrac{1}{c}=a+b+c,\)

(3)and

(4) \(\cfrac{a^{2}}{c}+\cfrac{b^{2}}{a}+\cfrac{c^{2}}{b}=a^{2} \cdot \cfrac{1}{c}+b^{2} \cdot \cfrac{1}{a}+c^{2} \cdot \cfrac{1}{b} \geq a^{2} \cdot \cfrac{1}{a}+b^{2} \cdot \cfrac{1}{b}+c^{2} \cdot \cfrac{1}{c}=a+b+c .\)

Adding (3) and (4) yields the required inequality. The equality occurs iff \(a=b=c\)

Example 4. Let \(x, y, z\) be positive real numbers. Prove the inequality

\[ \tfrac{x^{3}}{y z}+\tfrac{y^{3}}{z x}+\tfrac{z^{3}}{x y} \geq x+y+z \]

Solution: Since the given inequality is symmetric we may assume that \(x \geq y \geq z\). Then

\[ x^{3} \geq y^{3} \geq z^{3} \text { and } \tfrac{1}{y z} \geq \tfrac{1}{z x} \geq \tfrac{1}{x y} \]

By the rearrangment inequality we have

(5)\[ \tfrac{x^{3}}{y z}+\tfrac{y^{3}}{z x}+\tfrac{z^{3}}{x y}=x^{3} \cdot \tfrac{1}{y z}+y^{3} \cdot \tfrac{1}{z x}+z^{3} \cdot \tfrac{1}{x y} \geq x^{3} \cdot \tfrac{1}{x y}+y^{3} \cdot \tfrac{1}{y z}+z^{3} \cdot \tfrac{1}{z x}=\tfrac{x^{2}}{y}+\tfrac{y^{2}}{z}+\tfrac{z^{2}}{x} . \]

We will prove that

(6)\[ \tfrac{x^{2}}{y}+\tfrac{y^{2}}{z}+\tfrac{z^{2}}{x} \geq x+y+z \]

Let \(x \geq y \geq z\). Then \(x^{2} \geq y^{2} \geq z^{2}\) and \(\tfrac{1}{z} \geq \tfrac{1}{y} \geq \tfrac{1}{x}\) (since inequality (6) is cyclic, we need to consider the case \(z \geq y \geq x\) ).

By the rearrangment inequality we obtain

\[ \tfrac{x^{2}}{y}+\tfrac{y^{2}}{z}+\tfrac{z^{2}}{x} \geq \tfrac{x^{2}}{x}+\tfrac{y^{2}}{y}+\tfrac{z^{2}}{z}=x+y+z \]

The case when \(z \geq y \geq z\) is analogous to the previous one.

Now by (5) and (6) we obtain

\[ \tfrac{x^{3}}{y z}+\tfrac{y^{3}}{z x}+\tfrac{z^{3}}{x y} \geq x+y+z, \text { q.e.d. } \]

Equality occurs iff \(x=y=z\).

Example 5. (IMO 1964). Suppose that \(a, b, c\) a are the lenghts of the sides of a triangle. Prove that

\[ a^{2}(b+c-a)+b^{2}(a+c-b)+c^{2}(a+b-c) \leq 3 a b c . \]

Solution: Since the expression is a symmetric function of \(a, b\) a and \(c\), we can assume, without loss of generality, that \(c \leq b \leq a\). In this case, \(a(b+c-a) \leq b(a+c-b) \leq c(a+b-c)\). For instance, the first inequality could be proved in the following way:

\[ a(b+c-a) \leq b(a+c-b) \Leftrightarrow a b+a c-a^{2} \leq a b+b c-b^{2} \]

\[ \begin{aligned} & \Leftrightarrow(a-b) c \leq(a+b)(a-b) \\ & \Leftrightarrow(a-b)(a+b-c) \geq 0 \end{aligned} \]

By (2) of the rearrangement inequality, we have

\[ \begin{aligned} & a^{2}(b+c-a)+b^{2}(c+a-b)+c^{2}(a+b-c) \leq b c(b+c-a)+c b(c+a-b)+a c(a+b-c) \\ & a^{2}(b+c-a)+b^{2}(c+a-b)+c^{2}(a+b-c) \leq c a(b+c-a)+a b(c+a-b)+b c(a+b-c) \end{aligned} \]

Therefore, if follows after summing these inequalities, that:

\[ 2\left[a^{2}(b+c-a)+b^{2}(c+a-b)+c^{2}(a+b-c)\right] \leq 6 a b c \] i.e.

\[ a^{2}(b+c-a)+b^{2}(a+c-b)+c^{2}(a+b-c) \leq 3 a b c, \text { q.e.d. } \]

Equality holds iff \(a=b=c\) (equilateral triangle).

Example 6. (IMO 1983). Let \(a, b\) a and \(c\) be the lengths of the sides of a triangle. Prove that

\[ a^{2} b(a-b)+b^{2} c(b-c)+c^{2} a(c-a) \geq 0 \]

Solution: Consider the case \(c \leq b \leq a\) (the other casses are similar). As in the previous example, we have that

\[ a(b+c-a) \leq b(a+c-b) \leq c(a+b-c) \]

and since \(\tfrac{1}{a} \leq \tfrac{1}{b} \leq \tfrac{1}{c}\), using the inequality (1), we deduce, that:

\(\tfrac{1}{a} \cdot a(b+c-a)+\tfrac{1}{b} \cdot b(c+a-b)+\tfrac{1}{c} \cdot c(a+b-c) \geq \tfrac{1}{c} \cdot a(b+c-a)+\tfrac{1}{a} \cdot b(c+a-b)+\tfrac{1}{b} \cdot c(a+b-c)\).

Therefore,

\[ a+b+c \geq \tfrac{a(b-a)}{c}+\tfrac{b(c-b)}{a}+\tfrac{c(a-c)}{b}+a+b+c \]

It follows that

\[ \tfrac{a(b-a)}{c}+\tfrac{b(c-b)}{a}+\tfrac{c(a-c)}{b} \leq 0 . \] Multiplying by \(a b c\), we obtain

\[ a^{2} b(b-a)+b^{2} c(b-c)+c^{2} a(c-a) \geq 0, \text { q.e.d. } \] Remark 1. Four different proofs of this inequality could be found in (Arslanagić, 2005).

Example 7. Let \(a_{1}, a_{2}, \ldots, a_{n}\) be distinct positive integers. Show that

\[ \tfrac{a_{1}}{2}+\tfrac{a_{2}}{8}+\ldots+\tfrac{a_{n}}{n \cdot 2^{n}} \geq 1-\tfrac{1}{2^{n}} \]

Solution: Arrange \(a_{1}, a_{2}, \ldots, a_{n}\) in increasing order as \(b_{1}, b_{2}, \ldots, b_{n}\). Then \(b_{m} \geq n\) b because we have distinct positive integers. Since \(\tfrac{1}{2}, \tfrac{1}{8}, \ldots, \tfrac{1}{n \cdot 2^{n}}\), by the rearrangement inequality it follows that:

\[ \begin{gathered} \tfrac{a_{1}}{2}+\tfrac{a_{2}}{8}+\ldots+\tfrac{a_{n}}{n \cdot 2^{n}} \geq \tfrac{b_{1}}{2}+\tfrac{b_{2}}{8}+\ldots+\tfrac{b_{n}}{n \cdot 2^{n}} \\ \geq \tfrac{1}{2}+\tfrac{2}{8}+\ldots+\tfrac{n}{n \cdot 2^{n}} \\ =\tfrac{1}{2}+\tfrac{1}{4}+\ldots+\tfrac{1}{2^{n}} \\ =\tfrac{1}{2}\left(1+\tfrac{1}{2}+\ldots+\tfrac{1}{2^{n-1}}\right) \\ =\tfrac{1}{2} \cdot \tfrac{1-\tfrac{1}{2^{n}}}{1-\tfrac{1}{2}}=1-\tfrac{1}{2^{n}}, \text { q.e.d. } \end{gathered} \]

Equality holds true iff \(a_{1}=1, a_{2}=2, \ldots, a_{n}=n\).

Example 8. (West German Math Olympiad, 1982). If \(a_{1}, a_{2}, \ldots, a_{n} \gt 0\) a and \(a=a_{1}+a_{2}+\ldots+a_{n}\); then

\[ \sum_{i=1}^{n} \tfrac{a_{i}}{2 a-a_{i}} \geq \tfrac{n}{2 n-1} \] Solution: By symmetry we may assume that \(a_{1} \geq a_{2} \geq \ldots \geq a_{n}\). Then \[ \tfrac{1}{2 a-a_{n}} \leq \ldots \leq \tfrac{1}{2 a-a_{1}} \] For convenience let \(a_{i}=a_{j}\) i if \(i \equiv j(\bmod n)\). For \(m=0,1, \ldots, n-1\) by the rearrangement inequality we get

\[ \sum_{i=1}^{n} \tfrac{a_{m+i}}{2 a-a_{i}} \leq \sum_{i=1}^{n} \tfrac{a_{i}}{2 a-a_{i}} \]

Adding these \(n\) inequalities we have

\[ \sum_{i=1}^{n} \tfrac{a}{2 a-a_{i}} \leq \sum_{i=1}^{n} \tfrac{n a_{i}}{2 a-a_{i}} . \]

Since

\[ \tfrac{a}{2 a-a_{i}}=\tfrac{1}{2}+\tfrac{1}{2} \cdot \tfrac{a_{i}}{2 a-a_{i}}, \] we get

\[ \tfrac{n}{2}+\tfrac{1}{2} \sum_{i=1}^{n} \tfrac{a_{i}}{2 a-a_{i}} \leq n \sum_{i=1}^{n} \tfrac{a_{i}}{2 a-a_{i}} \]

From here we obtain the desired inequality.

Equality holds iff \(a_{1}=a_{2}=\ldots=a_{n}=1\).

Example 9. If \(a, b, c \gt 0\), prove tha

\[ \tfrac{a^{3}}{b+c}+\tfrac{b^{3}}{c+a}+\tfrac{c^{3}}{a+b} \geq \tfrac{a^{2}+b^{2}+c^{2}}{2} \]

Solution: By symmetry we may assume that \(a \leq b \leq c\). Then \(a+b \leq c+a \leq b+c\). So, we have

\[ \tfrac{1}{b+c} \leq \tfrac{1}{c+a} \leq \tfrac{1}{a+b} \]

By the rearrangement inequality we have

\[ \begin{aligned} & \tfrac{a^{3}}{a+b}+\tfrac{b^{3}}{b+c}+\tfrac{c^{3}}{c+a} \leq \tfrac{a^{3}}{b+c}+\tfrac{b^{3}}{c+a}+\tfrac{c^{3}}{a+b} \\ & \tfrac{a^{3}}{c+a}+\tfrac{b^{3}}{a+b}+\tfrac{c^{3}}{b+c} \leq \tfrac{a^{3}}{b+c}+\tfrac{b^{3}}{c+a}+\tfrac{c^{3}}{a+b} \end{aligned} \]

Adding these inequalities and then dividing by 2, we get

\[ \tfrac{1}{2}\left(\tfrac{a^{3}+b^{3}}{a+b}+\tfrac{b^{3}+c^{3}}{b+c}+\tfrac{c^{3}+a^{3}}{c+a}\right) \leq \tfrac{a^{3}}{b+c}+\tfrac{b^{3}}{c+a}+\tfrac{c^{3}}{a+b} \]

Finally, since

\[ \tfrac{x^{3}+y^{3}}{x+y}=x^{2}-x y+y^{2} \geq \tfrac{x^{2}+y^{2}}{2} \] we have

\(\tfrac{a^{2}+b^{2}+c^{2}}{2}=\tfrac{1}{2}\left(\tfrac{a^{2}+b^{2}}{2}+\tfrac{b^{2}+c^{2}}{2}+\tfrac{c^{2}+a^{2}}{2}\right) \leq \tfrac{1}{2}\left(\tfrac{a^{3}+b^{3}}{a+b}+\tfrac{b^{3}+c^{3}}{b+c}+\tfrac{c^{3}+a^{3}}{c+a}\right) \leq \tfrac{a^{3}}{b+c}+\tfrac{b^{3}}{c+a}+\tfrac{c^{3}}{a+b}\), i.e.

\[ \tfrac{a^{3}}{b+c}+\tfrac{b^{3}}{c+a}+\tfrac{c^{3}}{a+b} \geq \tfrac{a^{2}+b^{2}+c^{2}}{2}, \text { q.e.d. } \] Equality holds true iff \(a=b=c\).

REFERENCES

Arslanagić, Š. (2005). Matematika za nadarene. Sarajevo: Bosanska riječ.

Cvetkovski, Z. (2012). Inequalities - Theorems, Techniques ans Selected Problems. Berlin, Heidelberg: Springer Verlag.

Engel, A. (1998). Problem-Solving Strategies. New York: Springer Verlag.

Ganga, M. (1991). Teme si probleme de matematica. Bucuresti: Editura Tehnica.

Hanjš, Ž. (2017). Međunarodne metematičke olimpijade. Zagreb: Element.

Grozdev, S. (2007). For High Achievements in Mathematics: The Bulgaria Experience (Theory and Practice). Sofia: ADE (ISBN 978-954-921391-1).

Hung, P. K. (2007). Secrets in Inequalities, Volume 1 – basic Inequalities. Zalau (Romania): GIL Publishing House.

Malčeski, R. (2016). Elementarni algebarski i analitički neravenstva. Skopje Sojuz na matematičari na Makedonija.