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[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).



An inequality for rearrangement-style sums
Let me prove it for $p=3$ (only because the notations look more friendly.) The maximum of left hand side is realized when the arrays $(a\_i),(b\_{\sigma(i)}),(c\_{\tau(i)})$ are equally sorted, so let us assume that it is the case. 


I claim that not only the sum, but the $s$-th largest summand of RHS (clarification: first largest means maximal) is not less than the $s$-th largest summand in LHS, for any $s=1,2,\dots,n$. Denote by $\alpha, \beta, \gamma$ the $s$-th largest elements of the arrays $a, b, c$ respectively. Choose minimal indices $i, j, k$ respectively for which $a\_i\geqslant \alpha$, $b\_j\geqslant \beta$, $c\_k\geqslant \gamma$. Without loss of generality $k=\max(i, j, k) $. Choose any $r$ such that $c\_r\geqslant \gamma$. We have $r\geqslant k\geqslant \max(i,j)$, therefore
$m\_r\geqslant a\_i b\_j c\_r\geqslant \alpha \beta \gamma$. We get at least $s$ such values of $r$, thus $s$-th largest $m$ is not less than $\alpha \beta\gamma$, as desired. 


