% completed, unproofread.
% -------------------------------------------------------------
% NOTE ON THE DETAILED AND SHORT VERSIONS:
% -------------------------------------------------------------
% This paper comes in two versions, a detailed and a short one.
% The short version should be more than sufficient for any
% reasonable use; the detailed one was written purely to
% convince the author of its correctness.
% To switch between the two versions, find the line containing
% "\newenvironment{noncompile}{}{}" in this LaTeX file.
% Look at the two lines right beneath this line.
% To compile the detailed version, they should be as follows:
%   \includecomment{verlong}
%   \excludecomment{vershort}
% To compile the short version, they should be as follows:
%   \excludecomment{verlong}
%   \includecomment{vershort}
% As a rule, the line
%   \excludecomment{noncompile}
% should stay as it is.

\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{framed}
\usepackage{comment}
\usepackage[breaklinks=True]{hyperref}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{amsthm}
\usepackage{needspace}
\usepackage{tabls}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{CSTFile=LaTeX article (bright).cst}
%TCIDATA{Created=Sat Mar 27 17:33:36 2004}
%TCIDATA{LastRevised=Wednesday, April 29, 2026 21:51:17}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fineprint}{\begin{small}}{\end{small}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{question}[1][Question]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\voffset=0cm
\hoffset=-0.7cm
\setlength\textheight{22.5cm}
\setlength\textwidth{15.5cm}
\newcommand\arxiv[1]{\href{http://www.arxiv.org/abs/#1}{\texttt{arXiv:#1}}}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\includecomment{verlong}
\excludecomment{vershort}
\excludecomment{noncompile}
\ihead{A problem on maxima and rearrangements}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\title{A problem on maxima and rearrangements}
\author{Darij Grinberg}
\date{version 0.3, 2 February 2019 (typos fixed 29 April 2026)}
\maketitle

\textit{Note:} The following problem was published as problem \textbf{O222} in
\textbf{Mathematical Reflections 2012/1}.

\subsubsection*{Problem}

Let $n\in\mathbb{N}$.

Let $a_{1}$, $a_{2}$, $...$, $a_{n}$ be $n$ nonnegative reals.

Let $b_{1}$, $b_{2}$, $...$, $b_{n}$ be $n$ nonnegative reals.

Let $\sigma$ be a permutation of $\left\{  1,2,...,n\right\}  $.

For every $k\in\left\{  1,2,...,n\right\}  $, let $c_{k}=\max\left(  \left\{
a_{1}b_{k},a_{2}b_{k},...,a_{k}b_{k}\right\}  \cup\left\{  a_{k}b_{1}%
,a_{k}b_{2},...,a_{k}b_{k}\right\}  \right)  $.

Prove that%
\[
a_{1}b_{\sigma\left(  1\right)  }+a_{2}b_{\sigma\left(  2\right)  }%
+...+a_{n}b_{\sigma\left(  n\right)  }\leq c_{1}+c_{2}+...+c_{n}.
\]


\subsubsection*{Remark}

\textbf{1)} By the rearrangement inequality, it is enough to prove this
inequality when $\sigma$ is the permutation (or, more precisely, one of the
permutations) which makes the sequences $\left(  a_{1},a_{2},...,a_{n}\right)
$ and $\left(  b_{\sigma\left(  1\right)  },b_{\sigma\left(  2\right)
},...,b_{\sigma\left(  n\right)  }\right)  $ equally sorted (because if we
treat $a_{1}$, $a_{2}$, $...$, $a_{n}$ and $b_{1}$, $b_{2}$, $...$, $b_{n}$ as
constants, then this permutation $\sigma$ maximizes the left hand side
$a_{1}b_{\sigma\left(  1\right)  }+a_{2}b_{\sigma\left(  2\right)  }%
+...+a_{n}b_{\sigma\left(  n\right)  }$ of our inequality, whereas the right
hand side is constant). But I don't think this helps in solving the problem.
It is actually putting the cart before the horse: The rearrangement inequality
can be derived from our problem (see the remark after the solution for details).

\textbf{2)} The problem was conceived by me as a lemma to prove the
\textquotedblleft combinatorialist's Chebyshev inequality\textquotedblright,
which states that $\left(  a_{1}+a_{2}+...+a_{n}\right)  \left(  b_{1}%
+b_{2}+...+b_{n}\right)  \leq n\left(  c_{1}+c_{2}+...+c_{n}\right)  $ (under
the conditions of the problem) and is due to Ahlswede and Blinovsky
(\cite[Lecture 15, Consequences of Theorem 33, no. 2]{1}). This inequality can
be derived from our problem by summing the left hand side over $\sigma\in
C_{n}$ (where $C_{n}$ denotes the subgroup of the symmetric group $S_{n}$
formed by all powers of the $n$-cycle $\left(  1,2,\ldots,n\right)  $). We
leave the details to the reader. The proof in \cite{1} is completely different.

\subsubsection*{Solution of the problem}

We begin with a simple lemma:

\begin{quote}
\textbf{Lemma 1.} Let $a$, $a^{\prime}$, $b$ and $b^{\prime}$ be four
nonnegative reals. Then,%
\begin{equation}
ab^{\prime}+a^{\prime}b\leq ab+\max\left\{  ab^{\prime},a^{\prime}b^{\prime
},a^{\prime}b\right\}  . \label{1}%
\end{equation}



\end{quote}

(Note that this lemma 1 is the particular case of our problem when $n=2$ and
$\sigma$ is the transposition $\left(  1,2\right)  $.)

\begin{proof}
[Proof of Lemma 1.]We distinguish between three cases:

\textit{Case 1.} We have $a\geq a^{\prime}$.

\textit{Case 2.} We have $b\geq b^{\prime}$.

\textit{Case 3.} We have neither $a\geq a^{\prime}$ nor $b\geq b^{\prime}$.

In Case 1, we have $a\geq a^{\prime}$ and thus%
\[
\underbrace{ab^{\prime}}_{\leq\max\left\{  ab^{\prime},a^{\prime}b^{\prime
},a^{\prime}b\right\}  }+\underbrace{a^{\prime}}_{\leq a}b\leq\max\left\{
ab^{\prime},a^{\prime}b^{\prime},a^{\prime}b\right\}  +ab=ab+\max\left\{
ab^{\prime},a^{\prime}b^{\prime},a^{\prime}b\right\}  .
\]
Thus, (\ref{1}) is proven in Case 1.

In Case 2, we have $b\geq b^{\prime}$ and thus%
\[
a\underbrace{b^{\prime}}_{\leq b}+\underbrace{a^{\prime}b}_{\leq\max\left\{
ab^{\prime},a^{\prime}b^{\prime},a^{\prime}b\right\}  }\leq ab+\max\left\{
ab^{\prime},a^{\prime}b^{\prime},a^{\prime}b\right\}  .
\]
Thus, (\ref{1}) is proven in Case 2.

Now let us consider Case 3. In this Case, we have neither $a\geq a^{\prime}$
nor $b\geq b^{\prime}$. Thus, $a<a^{\prime}$ and $b<b^{\prime}$. Hence,
$\underbrace{a}_{<a^{\prime}}-\,a^{\prime}<a^{\prime}-a^{\prime}=0$ and
$\underbrace{b}_{<b^{\prime}}-\,b^{\prime}<b^{\prime}-b^{\prime}=0$.
Therefore, $\left(  a-a^{\prime}\right)  \left(  b-b^{\prime}\right)  >0$
(since the product of two negative reals must always be positive), so that%
\begin{align*}
0 &  <\left(  a-a^{\prime}\right)  \left(  b-b^{\prime}\right)
=ab+\underbrace{a^{\prime}b^{\prime}}_{\leq\max\left\{  ab^{\prime},a^{\prime
}b^{\prime},a^{\prime}b\right\}  }-ab^{\prime}-a^{\prime}b\\
&  \leq ab+\max\left\{  ab^{\prime},a^{\prime}b^{\prime},a^{\prime}b\right\}
-ab^{\prime}-a^{\prime}b.
\end{align*}
This rewrites as%
\[
ab^{\prime}+a^{\prime}b\leq ab+\max\left\{  ab^{\prime},a^{\prime}b^{\prime
},a^{\prime}b\right\}  .
\]
Thus, (\ref{1}) is proven in Case 3.

We thus have proven (\ref{1}) in all Cases 1, 2 and 3. Since these cases are
clearly the only possible cases to occur, this shows that (\ref{1}) always
holds. This proves Lemma 1.
\end{proof}

Now, we need a trivial lemma from combinatorics:

\begin{quote}
\textbf{Lemma 2.} Let $N$ be a positive integer, and let $\sigma$ be a
permutation of $\left\{  1,2,...,N\right\}  $ such that $\sigma\left(
N\right)  =N$. Then, there exists a permutation $\tau$ of $\left\{
1,2,...,N-1\right\}  $ such that
\begin{equation}
\left(  \sigma\left(  i\right)  =\tau\left(  i\right)
\ \ \ \ \ \ \ \ \ \ \text{for every }i\in\left\{  1,2,...,N-1\right\}
\right)  . \label{2}%
\end{equation}



\end{quote}

\begin{verlong}
\begin{proof}
[Proof of Lemma 2.]For every $i\in\left\{  1,2,...,N-1\right\}  $, we have
$\sigma\left(  i\right)  \in\left\{  1,2,...,N-1\right\}  $%
\ \ \ \ \footnote{\textit{Proof.} Let $i\in\left\{  1,2,...,N-1\right\}  $.
Then, $i\leq N-1<N$, so that $i\neq N$, so that $\sigma\left(  i\right)
\neq\sigma\left(  N\right)  $ (because $\sigma$ is a permutation and thus
injective). Combining $\sigma\left(  i\right)  \in\left\{  1,2,\ldots
,N\right\}  $ with $\sigma\left(  i\right)  \neq\sigma\left(  N\right)  =N$,
we obtain $\sigma\left(  i\right)  \in\left\{  1,2,\ldots,N\right\}
\setminus\left\{  N\right\}  =\left\{  1,2,...,N-1\right\}  $, qed.}. Hence,
we can define a map $\tau:\left\{  1,2,...,N-1\right\}  \rightarrow\left\{
1,2,...,N-1\right\}  $ by%
\[
\left(  \tau\left(  u\right)  =\sigma\left(  u\right)  \text{ for every }%
u\in\left\{  1,2,...,N-1\right\}  \right)  ).
\]
This map $\tau$ is injective\footnote{\textit{Proof.} Let $u$ and $v$ be two
elements of $\left\{  1,2,...,N-1\right\}  $ such that $\tau\left(  u\right)
=\tau\left(  v\right)  $. Then, by the definition of $\tau$, we have
$\tau\left(  u\right)  =\sigma\left(  u\right)  $ and $\tau\left(  v\right)
=\sigma\left(  v\right)  $, so that $\sigma\left(  u\right)  =\tau\left(
u\right)  =\tau\left(  v\right)  =\sigma\left(  v\right)  $, so that $u=v$
(since $\sigma$ is a permutation and thus injective). Thus, we have shown that
any two elements $u$ and $v$ of $\left\{  1,2,...,N-1\right\}  $ such that
$\tau\left(  u\right)  =\tau\left(  v\right)  $ must satisfy $u=v$. In other
words, $\tau$ is injective, qed.} and surjective\footnote{\textit{Proof.} Let
$p\in\left\{  1,2,...,N-1\right\}  $. Then, $p\leq N-1<N$. Moreover,
$p\in\left\{  1,2,...,N-1\right\}  \subseteq\left\{  1,2,...,N\right\}  $, so
that $\sigma^{-1}\left(  p\right)  $ is well-defined. We have $\sigma
^{-1}\left(  p\right)  \neq N$ (because if $\sigma^{-1}\left(  p\right)  $
were $=N$, then $p$ would be $=\sigma\left(  N\right)  =N$, contradicting
$p<N$). Combining $\sigma^{-1}\left(  p\right)  \in\left\{  1,2,...,N\right\}
$ with $\sigma^{-1}\left(  p\right)  \neq N$, we obtain $\sigma^{-1}\left(
p\right)  \in\left\{  1,2,...,N\right\}  \setminus\left\{  N\right\}
=\left\{  1,2,...,N-1\right\}  $. Thus, $\tau\left(  \sigma^{-1}\left(
p\right)  \right)  $ is well-defined. By the definition of $\tau$, we have
$\tau\left(  \sigma^{-1}\left(  p\right)  \right)  =\sigma\left(  \sigma
^{-1}\left(  p\right)  \right)  =p$, and thus $p=\tau\left(  \sigma
^{-1}\left(  p\right)  \right)  \in\tau\left(  \left\{  1,2,...,N-1\right\}
\right)  $.
\par
So we have proven that every $p\in\left\{  1,2,...,N-1\right\}  $ satisfies
$p\in\tau\left(  \left\{  1,2,...,N-1\right\}  \right)  $. In other words,
$\tau$ is surjective.}, thus bijective. Hence, $\tau$ is a permutation of
$\left\{  1,2,...,N-1\right\}  $. Every $i\in\left\{  1,2,...,N-1\right\}  $
satisfies $\tau\left(  i\right)  =\sigma\left(  i\right)  $ (by the definition
of $\tau$). This proves Lemma 2.
\end{proof}
\end{verlong}

Now, we come to the actual \textit{solution of the problem}:

\begin{proof}
[Solution of the problem.]We will solve the problem by induction over $n$:

\textit{Induction base:} In the case $n=0$, the problem is evidently
true.\footnote{\textit{Proof.} In the case $n=0$, the inequality
\[
a_{1}b_{\sigma\left(  1\right)  }+a_{2}b_{\sigma\left(  2\right)  }%
+...+a_{n}b_{\sigma\left(  n\right)  }\leq c_{1}+c_{2}+...+c_{n}%
\]
takes the form $0\leq0$, which is obviously true. Thus, in the case $n=0$, the
problem is true.} This completes the induction base.

\textit{Induction step:} Fix some integer $N\geq1$. Assume that the problem
has already been solved for $n=N-1$. Now we need to solve the problem for
$n=N$.

Let $a_{1}$, $a_{2}$, $...$, $a_{N}$ be $N$ nonnegative reals.

Let $b_{1}$, $b_{2}$, $...$, $b_{N}$ be $N$ nonnegative reals.

Let $\sigma$ be a permutation of $\left\{  1,2,...,N\right\}  $.

For every $k\in\left\{  1,2,...,N\right\}  $, let $c_{k}=\max\left(  \left\{
a_{1}b_{k},a_{2}b_{k},...,a_{k}b_{k}\right\}  \cup\left\{  a_{k}b_{1}%
,a_{k}b_{2},...,a_{k}b_{k}\right\}  \right)  $.

We must then prove that%
\begin{equation}
a_{1}b_{\sigma\left(  1\right)  }+a_{2}b_{\sigma\left(  2\right)  }%
+...+a_{N}b_{\sigma\left(  N\right)  }\leq c_{1}+c_{2}+...+c_{N}.
\label{sol.1}%
\end{equation}


We distinguish between two cases:

\textit{Case 1:} We have $\sigma\left(  N\right)  =N$.

\textit{Case 2:} We have $\sigma\left(  N\right)  \neq N$.

First, let us consider Case 1. In this case, $\sigma\left(  N\right)  =N$, so
that Lemma 2 yields that there exists a permutation $\tau$ of $\left\{
1,2,...,N-1\right\}  $ such that%
\begin{equation}
\left(  \sigma\left(  i\right)  =\tau\left(  i\right)
\ \ \ \ \ \ \ \ \ \ \text{for every }i\in\left\{  1,2,...,N-1\right\}
\right)  . \label{sol.1A}%
\end{equation}
Consider this $\tau$.

We assumed that the problem has already been solved for $n=N-1$. Hence, we can
apply the problem to $\tau$ and $N-1$ instead of $\sigma$ and $n$, and obtain%
\begin{equation}
a_{1}b_{\tau\left(  1\right)  }+a_{2}b_{\tau\left(  2\right)  }+...+a_{N-1}%
b_{\tau\left(  N-1\right)  }\leq c_{1}+c_{2}+...+c_{N-1}. \label{sol.2A}%
\end{equation}


The definition of $c_{N}$ yields
\begin{align}
c_{N}  &  =\max\left(  \left\{  a_{1}b_{N},a_{2}b_{N},...,a_{N}b_{N}\right\}
\cup\left\{  a_{N}b_{1},a_{N}b_{2},...,a_{N}b_{N}\right\}  \right) \nonumber\\
&  \geq a_{N}b_{\sigma\left(  N\right)  } \label{sol.2H}%
\end{align}
(since $a_{N}b_{\sigma\left(  N\right)  }\in\left\{  a_{N}b_{1},a_{N}%
b_{2},...,a_{N}b_{N}\right\}  \subseteq\left\{  a_{1}b_{N},a_{2}%
b_{N},...,a_{N}b_{N}\right\}  \cup\left\{  a_{N}b_{1},a_{N}b_{2}%
,...,a_{N}b_{N}\right\}  $).

We can rewrite (\ref{sol.1A}) as follows: $\tau\left(  1\right)
=\sigma\left(  1\right)  $, $\tau\left(  2\right)  =\sigma\left(  2\right)  $,
$...$, $\tau\left(  N-1\right)  =\sigma\left(  N-1\right)  $. Thus,
(\ref{sol.2A}) becomes%
\[
a_{1}b_{\sigma\left(  1\right)  }+a_{2}b_{\sigma\left(  2\right)
}+...+a_{N-1}b_{\sigma\left(  N-1\right)  }\leq c_{1}+c_{2}+...+c_{N-1}.
\]
Adding this inequality to the inequality $a_{N}b_{\sigma\left(  N\right)
}\leq c_{N}$ (which follows from (\ref{sol.2H})), we obtain%
\[
a_{1}b_{\sigma\left(  1\right)  }+a_{2}b_{\sigma\left(  2\right)
}+...+a_{N-1}b_{\sigma\left(  N-1\right)  }+a_{N}b_{\sigma\left(  N\right)
}\leq c_{1}+c_{2}+...+c_{N-1}+c_{N}.
\]
In other words, (\ref{sol.1}) holds. We have thus proven (\ref{sol.1}) in Case 1.

Next, let us consider Case 2. In this case, $\sigma\left(  N\right)  \neq N$.

Let $j=\sigma^{-1}\left(  N\right)  $. Thus, $j=\sigma^{-1}\left(  N\right)
\neq N$, so that $j\in\left\{  1,2,...,N-1\right\}  $.

Let $\eta$ be the permutation $\sigma\circ\left(  N,j\right)  $ of $\left\{
1,2,...,N\right\}  $ (where $\left(  N,j\right)  $ is the transposition which
transposes $N$ with $j$). Then,
\[
\eta\left(  N\right)  =\left(  \sigma\circ\left(  N,j\right)  \right)  \left(
N\right)  =\sigma\underbrace{\left(  \left(  N,j\right)  \left(  N\right)
\right)  }_{\substack{=j\\\text{(by the definition of }\left(  N,j\right)
\text{)}}}=\sigma\left(  j\right)  =N
\]
(since $j=\sigma^{-1}\left(  N\right)  $). Hence, Lemma 2 (applied to $\eta$
instead of $\sigma$) yields that there exists a permutation $\tau$ of
$\left\{  1,2,...,N-1\right\}  $ such that%
\begin{equation}
\left(  \eta\left(  i\right)  =\tau\left(  i\right)
\ \ \ \ \ \ \ \ \ \ \text{for every }i\in\left\{  1,2,...,N-1\right\}
\right)  . \label{sol.1B}%
\end{equation}
Consider this $\tau$.

We assumed that the problem has already been solved for $n=N-1$. Hence, we can
apply the problem to $\tau$ and $N-1$ instead of $\sigma$ and $n$, and obtain%
\begin{equation}
a_{1}b_{\tau\left(  1\right)  }+a_{2}b_{\tau\left(  2\right)  }+...+a_{N-1}%
b_{\tau\left(  N-1\right)  }\leq c_{1}+c_{2}+...+c_{N-1}. \label{sol.2B}%
\end{equation}


But for every $i\in\left\{  1,2,...,N-1\right\}  \diagdown\left\{  j\right\}
$, we have%
\begin{align}
&  \tau\left(  i\right) \nonumber\\
&  =\eta\left(  i\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{by (\ref{sol.1B}),
since }i\in\left\{  1,2,...,N-1\right\}  \diagdown\left\{  j\right\}
\subseteq\left\{  1,2,...,N-1\right\}  \right) \nonumber\\
&  =\left(  \sigma\circ\left(  N,j\right)  \right)  \left(  i\right)
\ \ \ \ \ \ \ \ \ \ \left(  \text{since }\eta=\sigma\circ\left(  N,j\right)
\right) \nonumber\\
&  =\sigma\left(  \left(  N,j\right)  \left(  i\right)  \right)
=\sigma\left(  i\right) \label{sol.3B}\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{since }\\
i\in\underbrace{\left\{  1,2,...,N-1\right\}  }_{=\left\{  1,2,...,N\right\}
\diagdown\left\{  N\right\}  }\diagdown\left\{  j\right\}  =\left(  \left\{
1,2,...,N\right\}  \diagdown\left\{  N\right\}  \right)  \diagdown\left\{
j\right\}  =\left\{  1,2,...,N\right\}  \diagdown\left\{  N,j\right\}
\text{,}\\
\text{and thus }i\notin\left\{  N,j\right\}  \text{, so that }\left(
N,j\right)  \left(  i\right)  =i\text{ (by the definition of }\left(
N,j\right)  \text{)}%
\end{array}
\right)  .\nonumber
\end{align}
On the other hand,%
\begin{align*}
\tau\left(  j\right)   &  =\eta\left(  j\right)  \ \ \ \ \ \ \ \ \ \ \left(
\text{by (\ref{sol.1B}), applied to }i=j\text{ (since }j\in\left\{
1,2,...,N-1\right\}  \text{)}\right) \\
&  =\left(  \sigma\circ\left(  N,j\right)  \right)  \left(  j\right)
\ \ \ \ \ \ \ \ \ \ \left(  \text{since }\eta=\sigma\circ\left(  N,j\right)
\right) \\
&  =\sigma\left(  \underbrace{\left(  N,j\right)  \left(  j\right)
}_{\substack{=N\\\text{(by the definition of }\left(  N,j\right)  \text{)}%
}}\right)  =\sigma\left(  N\right)  .
\end{align*}
Now,%
\begin{align*}
&  a_{1}b_{\tau\left(  1\right)  }+a_{2}b_{\tau\left(  2\right)  }%
+...+a_{N-1}b_{\tau\left(  N-1\right)  }\\
&  =\sum_{i\in\left\{  1,2,...,N-1\right\}  }a_{i}b_{\tau\left(  i\right)
}=a_{j}\underbrace{b_{\tau\left(  j\right)  }}_{\substack{=b_{\sigma\left(
N\right)  }\\\text{(since }\tau\left(  j\right)  =\sigma\left(  N\right)
\text{)}}}+\sum_{i\in\left\{  1,2,...,N-1\right\}  \diagdown\left\{
j\right\}  }a_{i}\underbrace{b_{\tau\left(  i\right)  }}_{\substack{=b_{\sigma
\left(  i\right)  }\\\text{(by (\ref{sol.3B}))}}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }j\in\left\{  1,2,...,N-1\right\}
\right) \\
&  =a_{j}b_{\sigma\left(  N\right)  }+\sum_{i\in\left\{  1,2,...,N-1\right\}
\diagdown\left\{  j\right\}  }a_{i}b_{\sigma\left(  i\right)  }.
\end{align*}
Hence, (\ref{sol.2B}) rewrites as%
\begin{equation}
a_{j}b_{\sigma\left(  N\right)  }+\sum_{i\in\left\{  1,2,...,N-1\right\}
\diagdown\left\{  j\right\}  }a_{i}b_{\sigma\left(  i\right)  }\leq
c_{1}+c_{2}+...+c_{N-1}. \label{sol.4B}%
\end{equation}
But%
\begin{align}
&  a_{1}b_{\sigma\left(  1\right)  }+a_{2}b_{\sigma\left(  2\right)
}+...+a_{N}b_{\sigma\left(  N\right)  }\nonumber\\
&  =\underbrace{\left(  a_{1}b_{\sigma\left(  1\right)  }+a_{2}b_{\sigma
\left(  2\right)  }+...+a_{N-1}b_{\sigma\left(  N-1\right)  }\right)
}_{\substack{=\sum\limits_{i\in\left\{  1,2,...,N-1\right\}  }a_{i}%
b_{\sigma\left(  i\right)  }=a_{j}b_{\sigma\left(  j\right)  }+\sum
\limits_{i\in\left\{  1,2,...,N-1\right\}  \diagdown\left\{  j\right\}  }%
a_{i}b_{\sigma\left(  i\right)  }\\\text{(since }j\in\left\{
1,2,...,N-1\right\}  \text{)}}}+a_{N}b_{\sigma\left(  N\right)  }\nonumber\\
&  =a_{j}\underbrace{b_{\sigma\left(  j\right)  }}_{=b_{N}\text{ (since
}\sigma\left(  j\right)  =N\text{)}}+\sum\limits_{i\in\left\{
1,2,...,N-1\right\}  \diagdown\left\{  j\right\}  }a_{i}b_{\sigma\left(
i\right)  }+a_{N}b_{\sigma\left(  N\right)  }\nonumber\\
&  =a_{j}b_{N}+\sum\limits_{i\in\left\{  1,2,...,N-1\right\}  \diagdown
\left\{  j\right\}  }a_{i}b_{\sigma\left(  i\right)  }+a_{N}b_{\sigma\left(
N\right)  }\nonumber\\
&  =\underbrace{a_{j}b_{N}+a_{N}b_{\sigma\left(  N\right)  }}_{\substack{\leq
a_{j}b_{\sigma\left(  N\right)  }+\max\left\{  a_{j}b_{N},a_{N}b_{N}%
,a_{N}b_{\sigma\left(  N\right)  }\right\}  \\\text{(by Lemma 1, applied to
}a=a_{j}\text{, }a^{\prime}=a_{N}\text{,}\\b=b_{\sigma\left(  N\right)
}\text{ and }b^{\prime}=b_{N}\text{)}}}+\sum\limits_{i\in\left\{
1,2,...,N-1\right\}  \diagdown\left\{  j\right\}  }a_{i}b_{\sigma\left(
i\right)  }\nonumber\\
&  \leq a_{j}b_{\sigma\left(  N\right)  }+\max\left\{  a_{j}b_{N},a_{N}%
b_{N},a_{N}b_{\sigma\left(  N\right)  }\right\}  +\sum\limits_{i\in\left\{
1,2,...,N-1\right\}  \diagdown\left\{  j\right\}  }a_{i}b_{\sigma\left(
i\right)  }\nonumber\\
&  =\underbrace{a_{j}b_{\sigma\left(  N\right)  }+\sum\limits_{i\in\left\{
1,2,...,N-1\right\}  \diagdown\left\{  j\right\}  }a_{i}b_{\sigma\left(
i\right)  }}_{\substack{\leq c_{1}+c_{2}+...+c_{N-1}\\\text{(by (\ref{sol.4B}%
))}}}+\max\left\{  a_{j}b_{N},a_{N}b_{N},a_{N}b_{\sigma\left(  N\right)
}\right\} \nonumber\\
&  \leq c_{1}+c_{2}+...+c_{N-1}+\max\left\{  a_{j}b_{N},a_{N}b_{N}%
,a_{N}b_{\sigma\left(  N\right)  }\right\}  . \label{sol.5B}%
\end{align}
But $\left\{  a_{j}b_{N},a_{N}b_{N},a_{N}b_{\sigma\left(  N\right)  }\right\}
\subseteq\left\{  a_{1}b_{N},a_{2}b_{N},...,a_{N}b_{N}\right\}  \cup\left\{
a_{N}b_{1},a_{N}b_{2},...,a_{N}b_{N}\right\}  $\ \ \ \ \footnote{This is
because%
\begin{align*}
a_{j}b_{N}  &  \in\left\{  a_{1}b_{N},a_{2}b_{N},...,a_{N}b_{N}\right\}
\subseteq\left\{  a_{1}b_{N},a_{2}b_{N},...,a_{N}b_{N}\right\}  \cup\left\{
a_{N}b_{1},a_{N}b_{2},...,a_{N}b_{N}\right\}  ;\\
a_{N}b_{N}  &  \in\left\{  a_{1}b_{N},a_{2}b_{N},...,a_{N}b_{N}\right\}
\subseteq\left\{  a_{1}b_{N},a_{2}b_{N},...,a_{N}b_{N}\right\}  \cup\left\{
a_{N}b_{1},a_{N}b_{2},...,a_{N}b_{N}\right\}  ;\\
a_{N}b_{\sigma\left(  N\right)  }  &  \in\left\{  a_{N}b_{1},a_{N}%
b_{2},...,a_{N}b_{N}\right\}  \subseteq\left\{  a_{1}b_{N},a_{2}%
b_{N},...,a_{N}b_{N}\right\}  \cup\left\{  a_{N}b_{1},a_{N}b_{2}%
,...,a_{N}b_{N}\right\}  .
\end{align*}
}, so that
\begin{align*}
\max\left\{  a_{j}b_{N},a_{N}b_{N},a_{N}b_{\sigma\left(  N\right)  }\right\}
&  \leq\max\left(  \left\{  a_{1}b_{N},a_{2}b_{N},...,a_{N}b_{N}\right\}
\cup\left\{  a_{N}b_{1},a_{N}b_{2},...,a_{N}b_{N}\right\}  \right) \\
&  =c_{N}%
\end{align*}
(since $c_{N}$ is defined as $\max\left(  \left\{  a_{1}b_{N},a_{2}%
b_{N},...,a_{N}b_{N}\right\}  \cup\left\{  a_{N}b_{1},a_{N}b_{2}%
,...,a_{N}b_{N}\right\}  \right)  $). Hence, (\ref{sol.5B}) becomes%
\begin{align*}
a_{1}b_{\sigma\left(  1\right)  }+a_{2}b_{\sigma\left(  2\right)  }%
+...+a_{N}b_{\sigma\left(  N\right)  }  &  \leq c_{1}+c_{2}+...+c_{N-1}%
+\underbrace{\max\left\{  a_{j}b_{N},a_{N}b_{N},a_{N}b_{\sigma\left(
N\right)  }\right\}  }_{\leq c_{N}}\\
&  \leq c_{1}+c_{2}+...+c_{N-1}+c_{N}=c_{1}+c_{2}+...+c_{N}.
\end{align*}
In other words, (\ref{sol.1}) holds. We have thus proven (\ref{sol.1}) in Case 2.

Since the cases 1 and 2 are the only possible cases, and since we have proven
(\ref{sol.1}) in both of these cases, we conclude that (\ref{sol.1}) is true.
We thus have shown that $a_{1}b_{\sigma\left(  1\right)  }+a_{2}%
b_{\sigma\left(  2\right)  }+...+a_{N}b_{\sigma\left(  N\right)  }\leq
c_{1}+c_{2}+...+c_{N}$. But this means that we have solved the problem for
$n=N$. This completes the induction step.

Thus, the induction proof of our problem is complete.
\end{proof}

\subsubsection*{Remark}

The problem that we just solved generalizes the rearrangement inequality. To
see why, here is one possible form of the rearrangement inequality:

\begin{quote}
\textbf{Corollary 3.} Let $n\in\mathbb{N}$.

Let $a_{1}$, $a_{2}$, $...$, $a_{n}$ be $n$ reals such that $a_{1}\leq
a_{2}\leq...\leq a_{n}$.

Let $b_{1}$, $b_{2}$, $...$, $b_{n}$ be $n$ reals such that $b_{1}\leq
b_{2}\leq...\leq b_{n}$.

Let $\sigma$ be a permutation of $\left\{  1,2,...,n\right\}  $.

Then,%
\[
a_{1}b_{\sigma\left(  1\right)  }+a_{2}b_{\sigma\left(  2\right)  }%
+...+a_{n}b_{\sigma\left(  n\right)  }\leq a_{1}b_{1}+a_{2}b_{2}%
+...+a_{n}b_{n}.
\]

\end{quote}

\begin{proof}
[Proof of Corollary 3.]This is trivial if $n=0$. Thus, we assume from now on
(without loss of generality) that $n\geq1$.

Let $\alpha=\min\left\{  a_{1},a_{2},...,a_{n}\right\}  $ and $\beta
=\min\left\{  b_{1},b_{2},...,b_{n}\right\}  $.

\begin{vershort}
For every $k\in\left\{  1,2,...,n\right\}  $, let $a_{k}^{\prime}=a_{k}%
-\alpha$ and $b_{k}^{\prime}=b_{k}-\beta$. Then, $a_{1}^{\prime}$,
$a_{2}^{\prime}$, $...$, $a_{n}^{\prime}$ are $n$ nonnegative reals, and so
are $b_{1}^{\prime}$, $b_{2}^{\prime}$, $...$, $b_{n}^{\prime}$.
\end{vershort}

\begin{verlong}
For every $k\in\left\{  1,2,...,n\right\}  $, let $a_{k}^{\prime}=a_{k}%
-\alpha$ and $b_{k}^{\prime}=b_{k}-\beta$. Then, every $k\in\left\{
1,2,...,n\right\}  $ satisfies $a_{k}^{\prime}=a_{k}-\underbrace{\alpha
}_{=\min\left\{  a_{1},a_{2},...,a_{n}\right\}  \leq a_{k}}\geq a_{k}-a_{k}%
=0$. In other words, $a_{1}^{\prime}$, $a_{2}^{\prime}$, $...$, $a_{n}%
^{\prime}$ are $n$ nonnegative reals. Similarly, $b_{1}^{\prime}$,
$b_{2}^{\prime}$, $...$, $b_{n}^{\prime}$ are $n$ nonnegative reals, i.e.,
every $k\in\left\{  1,2,...,n\right\}  $ satisfies $b_{k}^{\prime}\geq0$.
\end{verlong}

For every $k\in\left\{  1,2,...,n\right\}  $, let%
\[
c_{k}^{\prime}=\max\left(  \left\{  a_{1}^{\prime}b_{k}^{\prime},a_{2}%
^{\prime}b_{k}^{\prime},...,a_{k}^{\prime}b_{k}^{\prime}\right\}  \cup\left\{
a_{k}^{\prime}b_{1}^{\prime},a_{k}^{\prime}b_{2}^{\prime},...,a_{k}^{\prime
}b_{k}^{\prime}\right\}  \right)  .
\]
Then, the problem that we have solved (applied to $\left(  a_{1}^{\prime
},a_{2}^{\prime},...,a_{n}^{\prime}\right)  $, $\left(  b_{1}^{\prime}%
,b_{2}^{\prime},...,b_{n}^{\prime}\right)  $ and $\left(  c_{1}^{\prime}%
,c_{2}^{\prime},...,c_{n}^{\prime}\right)  $ instead of $\left(  a_{1}%
,a_{2},...,a_{n}\right)  $, $\left(  b_{1},b_{2},...,b_{n}\right)  $ and
$\left(  c_{1},c_{2},...,c_{n}\right)  $) yields%
\begin{equation}
a_{1}^{\prime}b_{\sigma\left(  1\right)  }^{\prime}+a_{2}^{\prime}%
b_{\sigma\left(  2\right)  }^{\prime}+...+a_{n}^{\prime}b_{\sigma\left(
n\right)  }^{\prime}\leq c_{1}^{\prime}+c_{2}^{\prime}+...+c_{n}^{\prime}.
\label{3.pf.0}%
\end{equation}


\begin{vershort}
However, notice that $a_{1}^{\prime}\leq a_{2}^{\prime}\leq...\leq
a_{n}^{\prime}$ (because of $a_{1}\leq a_{2}\leq...\leq a_{n}$) and
$b_{1}^{\prime}\leq b_{2}^{\prime}\leq...\leq b_{n}^{\prime}$ (similarly).
Thus, $c_{k}^{\prime}=a_{k}^{\prime}b_{k}^{\prime}$ for every $k\in\left\{
1,2,...,n\right\}  $ (since $c_{k}^{\prime}$ was defined as the maximum of the
set $\left\{  a_{1}^{\prime}b_{k}^{\prime},a_{2}^{\prime}b_{k}^{\prime
},...,a_{k}^{\prime}b_{k}^{\prime}\right\}  \cup\left\{  a_{k}^{\prime}%
b_{1}^{\prime},a_{k}^{\prime}b_{2}^{\prime},...,a_{k}^{\prime}b_{k}^{\prime
}\right\}  $, but this maximum is clearly $a_{k}^{\prime}b_{k}^{\prime}$ in
light of $a_{1}^{\prime}\leq a_{2}^{\prime}\leq...\leq a_{n}^{\prime}$ and
$b_{1}^{\prime}\leq b_{2}^{\prime}\leq...\leq b_{n}^{\prime}$). Thus,
$\sum\limits_{k=1}^{n}c_{k}^{\prime}=\sum\limits_{k=1}^{n}a_{k}^{\prime}%
b_{k}^{\prime}$.
\end{vershort}

\begin{verlong}
But now, it is easy to see that every $k\in\left\{  1,2,...,n\right\}  $
satisfies
\begin{equation}
c_{k}^{\prime}\leq a_{k}^{\prime}b_{k}^{\prime} \label{3.pf.1}%
\end{equation}
\footnote{\textit{Proof of (\ref{3.pf.1}).} Let $k\in\left\{
1,2,...,n\right\}  $. By definition of $c_{k}^{\prime}$, we have%
\begin{align*}
c_{k}^{\prime}  &  =\max\left(  \left\{  a_{1}^{\prime}b_{k}^{\prime}%
,a_{2}^{\prime}b_{k}^{\prime},...,a_{k}^{\prime}b_{k}^{\prime}\right\}
\cup\left\{  a_{k}^{\prime}b_{1}^{\prime},a_{k}^{\prime}b_{2}^{\prime
},...,a_{k}^{\prime}b_{k}^{\prime}\right\}  \right) \\
&  \in\left\{  a_{1}^{\prime}b_{k}^{\prime},a_{2}^{\prime}b_{k}^{\prime
},...,a_{k}^{\prime}b_{k}^{\prime}\right\}  \cup\left\{  a_{k}^{\prime}%
b_{1}^{\prime},a_{k}^{\prime}b_{2}^{\prime},...,a_{k}^{\prime}b_{k}^{\prime
}\right\}
\end{align*}
(since the maximum of a set always belongs to that set). Thus, either
$c_{k}^{\prime}\in\left\{  a_{1}^{\prime}b_{k}^{\prime},a_{2}^{\prime}%
b_{k}^{\prime},...,a_{k}^{\prime}b_{k}^{\prime}\right\}  $ or $c_{k}^{\prime
}\in\left\{  a_{k}^{\prime}b_{1}^{\prime},a_{k}^{\prime}b_{2}^{\prime
},...,a_{k}^{\prime}b_{k}^{\prime}\right\}  $ (or both). In other words, we
must be in one of the following two cases:
\par
\textit{Case 1.} We have $c_{k}^{\prime}\in\left\{  a_{1}^{\prime}%
b_{k}^{\prime},a_{2}^{\prime}b_{k}^{\prime},...,a_{k}^{\prime}b_{k}^{\prime
}\right\}  $.
\par
\textit{Case 2.} We have $c_{k}^{\prime}\in\left\{  a_{k}^{\prime}%
b_{1}^{\prime},a_{k}^{\prime}b_{2}^{\prime},...,a_{k}^{\prime}b_{k}^{\prime
}\right\}  $.
\par
Let us first consider Case 1. In this case, we have $c_{k}^{\prime}\in\left\{
a_{1}^{\prime}b_{k}^{\prime},a_{2}^{\prime}b_{k}^{\prime},...,a_{k}^{\prime
}b_{k}^{\prime}\right\}  $, so that there exists an $i\in\left\{
1,2,...,k\right\}  $ such that $c_{k}^{\prime}=a_{i}^{\prime}b_{k}^{\prime}$.
Consider such an $i$. Then, $i\in\left\{  1,2,...,k\right\}  $, so that $i\leq
k$ and thus $a_{i}\leq a_{k}$ (since $a_{1}\leq a_{2}\leq...\leq a_{n}$) and%
\begin{align*}
a_{i}^{\prime}  &  =\underbrace{a_{i}}_{\leq a_{k}}-\alpha
\ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of }a_{i}^{\prime}\right)
\\
&  \leq a_{k}-\alpha=a_{k}^{\prime}\ \ \ \ \ \ \ \ \ \ \left(  \text{since
}a_{k}^{\prime}=a_{k}-\alpha\text{ by the definition of }a_{k}^{\prime
}\right)  .
\end{align*}
Since $b_{k}^{\prime}\geq0$, this yields $a_{i}^{\prime}b_{k}^{\prime}\leq
a_{k}^{\prime}b_{k}^{\prime}$. Thus, $c_{k}^{\prime}=a_{i}^{\prime}%
b_{k}^{\prime}\leq a_{k}^{\prime}b_{k}^{\prime}$. So we have proven
$c_{k}^{\prime}\leq a_{k}^{\prime}b_{k}^{\prime}$ in Case 1.
\par
Now let us consider Case 2. In this case, we have $c_{k}^{\prime}\in\left\{
a_{k}^{\prime}b_{1}^{\prime},a_{k}^{\prime}b_{2}^{\prime},...,a_{k}^{\prime
}b_{k}^{\prime}\right\}  $, so that there exists an $i\in\left\{
1,2,...,k\right\}  $ such that $c_{k}^{\prime}=a_{k}^{\prime}b_{i}^{\prime}$.
Consider such an $i$. Then, $i\in\left\{  1,2,...,k\right\}  $, so that $i\leq
k$ and thus $b_{i}\leq b_{k}$ (since $b_{1}\leq b_{2}\leq...\leq b_{n}$) and%
\begin{align*}
b_{i}^{\prime}  &  =\underbrace{b_{i}}_{\leq b_{k}}-\beta
\ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of }b_{i}^{\prime}\right)
\\
&  \leq b_{k}-\beta=b_{k}^{\prime}\ \ \ \ \ \ \ \ \ \ \left(  \text{since
}b_{k}^{\prime}=b_{k}-\beta\text{ by the definition of }b_{k}^{\prime}\right)
.
\end{align*}
Since $a_{k}^{\prime}\geq0$, this yields $a_{k}^{\prime}b_{i}^{\prime}\leq
a_{k}^{\prime}b_{k}^{\prime}$. Thus, $c_{k}^{\prime}=a_{k}^{\prime}%
b_{i}^{\prime}\leq a_{k}^{\prime}b_{k}^{\prime}$. So we have proven
$c_{k}^{\prime}\leq a_{k}^{\prime}b_{k}^{\prime}$ in Case 2.
\par
Thus, we have proven $c_{k}^{\prime}\leq a_{k}^{\prime}b_{k}^{\prime}$ in each
of the two cases 1 and 2. Since these two cases are the only possible cases,
this yields that $c_{k}^{\prime}\leq a_{k}^{\prime}b_{k}^{\prime}$ always
holds. This proves (\ref{3.pf.1}).}. Hence, it is almost trivial that every
$k\in\left\{  1,2,...,n\right\}  $ satisfies $c_{k}^{\prime}=a_{k}^{\prime
}b_{k}^{\prime}\ \ \ \ $\footnote{\textit{Proof.} Let $k\in\left\{
1,2,...,n\right\}  $. Then,%
\[
a_{k}^{\prime}b_{k}^{\prime}\in\left\{  a_{1}^{\prime}b_{k}^{\prime}%
,a_{2}^{\prime}b_{k}^{\prime},...,a_{k}^{\prime}b_{k}^{\prime}\right\}
\subseteq\left\{  a_{1}^{\prime}b_{k}^{\prime},a_{2}^{\prime}b_{k}^{\prime
},...,a_{k}^{\prime}b_{k}^{\prime}\right\}  \cup\left\{  a_{k}^{\prime}%
b_{1}^{\prime},a_{k}^{\prime}b_{2}^{\prime},...,a_{k}^{\prime}b_{k}^{\prime
}\right\}  .
\]
Since every element of a set is always $\leq$ to the maximum of that set, this
yields%
\[
a_{k}^{\prime}b_{k}^{\prime}\leq\max\left(  \left\{  a_{1}^{\prime}%
b_{k}^{\prime},a_{2}^{\prime}b_{k}^{\prime},...,a_{k}^{\prime}b_{k}^{\prime
}\right\}  \cup\left\{  a_{k}^{\prime}b_{1}^{\prime},a_{k}^{\prime}%
b_{2}^{\prime},...,a_{k}^{\prime}b_{k}^{\prime}\right\}  \right)
=c_{k}^{\prime}.
\]
Combined with (\ref{3.pf.1}), this yields $c_{k}^{\prime}=a_{k}^{\prime}%
b_{k}^{\prime}$, qed.}. Thus, $\sum\limits_{k=1}^{n}c_{k}^{\prime}%
=\sum\limits_{k=1}^{n}a_{k}^{\prime}b_{k}^{\prime}$.
\end{verlong}

Now, (\ref{3.pf.0}) can be rewritten as%
\begin{align}
&  0\nonumber\\
&  \geq\underbrace{\left(  a_{1}^{\prime}b_{\sigma\left(  1\right)  }^{\prime
}+a_{2}^{\prime}b_{\sigma\left(  2\right)  }^{\prime}+...+a_{n}^{\prime
}b_{\sigma\left(  n\right)  }^{\prime}\right)  }_{=\sum\limits_{k=1}^{n}%
a_{k}^{\prime}b_{\sigma\left(  k\right)  }^{\prime}}-\underbrace{\left(
c_{1}^{\prime}+c_{2}^{\prime}+...+c_{n}^{\prime}\right)  }_{=\sum
\limits_{k=1}^{n}c_{k}^{\prime}=\sum\limits_{k=1}^{n}a_{k}^{\prime}%
b_{k}^{\prime}}\nonumber\\
&  =\sum\limits_{k=1}^{n}a_{k}^{\prime}b_{\sigma\left(  k\right)  }^{\prime
}-\sum\limits_{k=1}^{n}a_{k}^{\prime}b_{k}^{\prime}\nonumber\\
&  =\sum\limits_{k=1}^{n}\underbrace{a_{k}^{\prime}}_{\substack{=a_{k}%
-\alpha\\\text{(by the definition of }a_{k}^{\prime}\text{)}}}\left(
\underbrace{b_{\sigma\left(  k\right)  }^{\prime}}_{\substack{=b_{\sigma
\left(  k\right)  }-\beta\\\text{(by the definition of }b_{\sigma\left(
k\right)  }^{\prime}\text{)}}}-\underbrace{b_{k}^{\prime}}_{\substack{=b_{k}%
-\beta\\\text{(by the definition of }b_{k}^{\prime}\text{)}}}\right)
\nonumber\\
&  =\sum\limits_{k=1}^{n}\left(  a_{k}-\alpha\right)  \underbrace{\left(
\left(  b_{\sigma\left(  k\right)  }-\beta\right)  -\left(  b_{k}%
-\beta\right)  \right)  }_{=b_{\sigma\left(  k\right)  }-b_{k}}=\sum
\limits_{k=1}^{n}\underbrace{\left(  a_{k}-\alpha\right)  \left(
b_{\sigma\left(  k\right)  }-b_{k}\right)  }_{=a_{k}\left(  b_{\sigma\left(
k\right)  }-b_{k}\right)  -\alpha\left(  b_{\sigma\left(  k\right)  }%
-b_{k}\right)  }\nonumber\\
&  =\sum\limits_{k=1}^{n}\left(  a_{k}\left(  b_{\sigma\left(  k\right)
}-b_{k}\right)  -\alpha\left(  b_{\sigma\left(  k\right)  }-b_{k}\right)
\right)  =\sum\limits_{k=1}^{n}a_{k}\left(  b_{\sigma\left(  k\right)  }%
-b_{k}\right)  -\alpha\sum\limits_{k=1}^{n}\left(  b_{\sigma\left(  k\right)
}-b_{k}\right)  . \label{3.pf.2}%
\end{align}


\begin{vershort}
But since $\sigma$ is a permutation, we have $\sum\limits_{k=1}^{n}%
b_{\sigma\left(  k\right)  }=\sum\limits_{k=1}^{n}b_{k}$, so that%
\[
\sum\limits_{k=1}^{n}\left(  b_{\sigma\left(  k\right)  }-b_{k}\right)
=\underbrace{\sum\limits_{k=1}^{n}b_{\sigma\left(  k\right)  }}_{=\sum
\limits_{k=1}^{n}b_{k}}-\sum\limits_{k=1}^{n}b_{k}=\sum\limits_{k=1}^{n}%
b_{k}-\sum\limits_{k=1}^{n}b_{k}=0.
\]

\end{vershort}

\begin{verlong}
But since $\sigma$ is bijective (since $\sigma$ is a permutation), we have
$\sum\limits_{k\in\left\{  1,2,...,n\right\}  }b_{\sigma\left(  k\right)
}=\sum\limits_{k\in\left\{  1,2,...,n\right\}  }b_{k}$ (here, we substituted
$k$ for $\sigma\left(  k\right)  $ in the sum, since $\sigma$ is bijective),
so that%
\begin{align*}
\sum\limits_{k=1}^{n}\left(  b_{\sigma\left(  k\right)  }-b_{k}\right)   &
=\underbrace{\sum\limits_{k=1}^{n}b_{\sigma\left(  k\right)  }}_{=\sum
\limits_{k\in\left\{  1,2,...,n\right\}  }b_{\sigma\left(  k\right)  }%
=\sum\limits_{k\in\left\{  1,2,...,n\right\}  }b_{k}}-\underbrace{\sum
\limits_{k=1}^{n}b_{k}}_{=\sum\limits_{k\in\left\{  1,2,...,n\right\}
\ }b_{k}}\\
&  =\sum\limits_{k\in\left\{  1,2,...,n\right\}  \ }b_{k}-\sum\limits_{k\in
\left\{  1,2,...,n\right\}  \ }b_{k}=0.
\end{align*}

\end{verlong}

Thus, (\ref{3.pf.2}) becomes%
\begin{align*}
&  0\\
&  \geq\sum\limits_{k=1}^{n}a_{k}\left(  b_{\sigma\left(  k\right)  }%
-b_{k}\right)  -\alpha\underbrace{\sum\limits_{k=1}^{n}\left(  b_{\sigma
\left(  k\right)  }-b_{k}\right)  }_{=0}=\sum\limits_{k=1}^{n}a_{k}\left(
b_{\sigma\left(  k\right)  }-b_{k}\right)  -\alpha0\\
&  =\sum\limits_{k=1}^{n}a_{k}\left(  b_{\sigma\left(  k\right)  }%
-b_{k}\right)  =\underbrace{\sum\limits_{k=1}^{n}a_{k}b_{\sigma\left(
k\right)  }}_{=a_{1}b_{\sigma\left(  1\right)  }+a_{2}b_{\sigma\left(
2\right)  }+...+a_{n}b_{\sigma\left(  n\right)  }}-\underbrace{\sum
\limits_{k=1}^{n}a_{k}b_{k}}_{=a_{1}b_{1}+a_{2}b_{2}+...+a_{n}b_{n}}\\
&  =\left(  a_{1}b_{\sigma\left(  1\right)  }+a_{2}b_{\sigma\left(  2\right)
}+...+a_{n}b_{\sigma\left(  n\right)  }\right)  -\left(  a_{1}b_{1}+a_{2}%
b_{2}+...+a_{n}b_{n}\right)  .
\end{align*}
In other words,%
\[
a_{1}b_{\sigma\left(  1\right)  }+a_{2}b_{\sigma\left(  2\right)  }%
+...+a_{n}b_{\sigma\left(  n\right)  }\leq a_{1}b_{1}+a_{2}b_{2}%
+...+a_{n}b_{n}.
\]
This proves Corollary 3.
\end{proof}

\begin{thebibliography}{99999999}                                                                                         %


\bibitem[AhlBli08]{1}Rudolf Ahlswede, Vladimir Blinovsky, \textit{Lectures on
Advances in Combinatorics}, Springer 2008.
\end{thebibliography}


\end{document}