The following is a holdover from my math contest days that I never got around
to solve.

We will use the notation $\left[  k\right]  $ for the set $\left\{
1,2,\ldots,k\right\}  $ whenever $k$ is a nonnegative integer.

Let me first state my question in its general form, which is sadly not very
inviting. I recommend taking a look at the particular cases $p=2$ (proven) and
$p=3$ (open) stated further below (as Theorem 1 and Conjecture 2, respectively).
The $p=2$ case also comes with motivation.

> **Question.** Let $n$ and $p$ be two nonnegative integers. For each
$i\in\left[  n\right]  $ and $j\in\left[  p\right]  $, let $a_{i,j}$ be a
nonnegative real. For each $k\in\left[  n\right]  $, let
\begin{align}
m_{k}=\max\left\{  \prod_{j=1}^{p}a_{u_{j},j}\ \mid\ \left(  u_{1}
,u_{2},\ldots,u_{p}\right)  \in\left[  n\right]  ^{p};\ \max\left\{
u_{1},u_{2},\ldots,u_{p}\right\}  =k\right\}  .
\end{align}
Also, let $\sigma_{1},\sigma_{2},\ldots,\sigma_{p}$ be $p$ permutations of
$\left[  n\right]  $. Prove or disprove that
\begin{align}
\sum_{k=1}^{n}\prod_{j=1}^{p}a_{\sigma_{j}\left(  k\right)  ,j}\leq\sum
_{k=1}^{n}m_{k}.
\end{align}

This is easy to see for $n = 2$; I also have proven this for $p = 2$.
Experiments with Sage seem to suggest that the $n = 3$ and $p = 3$
case is also true.

One simple observation about the question is that if $\sigma$ is any
permutation of $\left[p\right]$, then replacing
$\sigma_1, \sigma_2, \ldots, \sigma_p$ by
$\sigma_1 \circ \sigma, \sigma_2 \circ \sigma, \ldots, \sigma_p \circ \sigma$
leaves the left hand side unchanged.
Thus, we can WLOG assume that $\sigma_1 = \operatorname{id}$.
This reduces the number of permutations involved to $p-1$.

**The case $p = 2$:** When $p = 2$, the question thus takes the following form (where we rename $a_{i,1}, a_{i,2}, \sigma_2$ as $a_i, b_i, \sigma$, respectively):

> **Theorem 1.** Let $a_1, a_2, \ldots, a_n$ be $n$ nonnegative reals.
>
> Let $b_1, b_2, \ldots, b_n$ be $n$ nonnegative reals.
> 
> For every $k\in\left[n\right]$, let $m_{k}=\max\left(  \left\{
a_{1}b_{k},a_{2}b_{k},\ldots,a_{k}b_{k}\right\}  \cup\left\{  a_{k}b_{1}%
,a_{k}b_{2},\ldots,a_{k}b_{k}\right\}  \right)  $.
> 
> Let $\sigma$ be a permutation of $\left[n\right]$.
> 
> Then,
\begin{align}
a_{1}b_{\sigma\left(  1\right)  }+a_{2}b_{\sigma\left(  2\right)  }
+\cdots+a_{n}b_{\sigma\left(  n\right)  }\leq m_1 + m_2 + \cdots + m_n.
\end{align}

This was problem O222 in Mathematical Reflections ([my proof](http://www.cip.ifi.lmu.de/~grinberg/maxperm.pdf)). I originally came up with it when trying to prove an inequality from [Ahlswede/Blinovsky](https://www.springer.com/us/book/9783540786016) (see [my proof](http://www.cip.ifi.lmu.de/~grinberg/maxperm.pdf) for details); but it also easily yields the classical rearrangement inequality. (In a sense, Theorem 1 relates to the Ahlswede/Blinovsky result as Chebyshev does to rearrangement.)

Note that the rearrangement inequality shows that the left hand side of the inequality in Theorem 1 is maximized (for fixed $n$, $a_i$ and $b_i$) when $\sigma$ has the property that the tuples $\left(a_1, a_2, \ldots, a_n\right)$ and $\left(b_{\sigma\left(1\right)}, b_{\sigma\left(2\right)}, \ldots, b_{\sigma\left(n\right)}\right)$ are equally sorted (i.e., we have $\left(a_i - a_j\right) \left(b_{\sigma\left(i\right)} - b_{\sigma\left(j\right)}\right) \geq 0$ for all $i$ and $j$). This observation did not end up useful in my proof of Theorem 1.

**The case $p = 3$:** To give some intuition for the Question above, let me state its $p = 3$ case as a conjecture (renaming $a_{i,1}, a_{i,2}, a_{i,3}, \sigma_2, \sigma_3$ as $a_i, b_i, c_i, \sigma, \tau$ and setting $\sigma_1 = \operatorname{id}$ as before):

> **Conjecture 2.** Let $a_1, a_2, \ldots, a_n$ be $n$ nonnegative reals.
>
> Let $b_1, b_2, \ldots, b_n$ be $n$ nonnegative reals.
> 
> Let $c_1, c_2, \ldots, c_n$ be $n$ nonnegative reals.
> 
> For every $k\in\left\{  1,2,\ldots,n\right\}  $, let $m_{k}=\max\left\{
a_{i}b_{j}c_{\ell}\ \mid\ \max\left\{  i,j,\ell\right\}  =k\right\}  $.
> 
> Let $\sigma$ and $\tau$ be two permutations of $\left[n\right]$.
> 
> Prove or disprove that
\begin{align}
a_{1}b_{\sigma\left(  1\right)  }c_{\tau\left(  1\right)  }+a_{2}
b_{\sigma\left(  2\right)  }c_{\tau\left(  2\right)  }+\cdots+a_{n}
b_{\sigma\left(  n\right)  }c_{\tau\left(  n\right)  }\leq m_{1}+m_{2}
+\cdots+m_{n}.
\end{align}

I believe that we can again use some sort of rearrangement inequality to maximize the left hand side of this inequality, but I don't expect this to be useful (nor am I fully sure about it -- [most treatments of rearrangement inequality for more than two tuples](https://www.math.ust.hk/excalibur/v19_n3.pdf) run into combinatorial troubles around the concept of "equally sorted" and equality cases).