Problem. (239MO 2019 11.7) Given positive $a_1,\ldots,a_n,b_1,\ldots,b_n,c_1,\ldots,c_n$. Let $m_k$ be the maximum product $a_ib_jc_l$ for triples $(i,j,l)$ satisfying $\max(i,j,l)=k$. Prove that $$ (a_1+\dots+a_n)(b_1+\dots+b_n)(c_1+\dots+c_n)\leqslant n^2(m_1+\dots+m_n).$$

Walkthrough. A lot of trivial stuff doesn’t work (as usual). The most naive bound gets you something like: $$LHS \le \sum_{i=1}^n (i^3 - (i-1)^3)m_i$$ which is a lot weaker than what we want: we use up too many $m_n$’s and have a ton of $m_1$’s leftover. In effect, we want to be fairly careful about how we swap out $a_ib_jc_k$ for $m$’s.

One productive observation is that the ``two-variable’’ case solves the general cases. Indeed, if $p_k= \max_{\max(i,j) =k} a_ib_j$, then $m_i = \max_{\max(i,j)=k} p_ic_j$, so: \begin{align*} (a_1+…a_n)(b_1+…+b_n)(c_1+…+c_n) &= n(p_1+…+p_n)(c_1+…+c_n)\ &= n^2(m_1+…+m_n) \end{align*} So we really should only focus on showing $$(a_1+...+a_n)(b_1+...+b_n) \le n(p_1+...+p_n)$$ At this stage you might already have some sense that this looks like Rearrangement or Chebyshev, but to make it solid we can stare at the $n=2$ case: $$(a_1+a_2)(b_1+b_2) \le 2(p_1+p_2)$$ Now we split cases:

• $a_1\le a_2$, $b_1\le b_2$: This is Chebyshev.
• $a_1 >a_2$, $b_1>b_2$: This is also Chebyshev, but it’s a lot weaker because the excess of $p_1 = a_1b_1$ is not a problem.
• $a_1 > a_2$ but $b_1\le b_2$: then $p_2 = a_1b_2$, so $2(p_1+p_2) = 2a_1(ba_1+b_2)\ge (a_1+a_2)(b_1+b_2)$.
• $a_1\le a_2$ and $b_1 > b_2$: similar to previous case

Now that we know how the $n=2$ case goes, we’re (rightfully!) more apprehensive to try the general $n$ case. But let’s try some reduction methods and see if they help.

Attempt 1: By keeping the RHS fixed, we can increase individual $a_i$ (or $b_i$) provided that none of the $\{p_k\}$ ``use’’ $a_i$ (or $b_i$). We can visualize this by drawing a $n\times n$ grid, and marking cell $(i,j)$ if $a_ib_j = p_{\max(i,j)}$, then by repeating this process we get that there is at least one marked cell per row/column. I didn’t find this very helpful because the conditions don’t really arrange themselves in a productive way.

Attempt 2: Let’s instead fix $LHS$, and think about $RHS$. Yikes, there are $\max$-es everywhere… but recall that if you have (multiset) $S$ and you start replacing subsets of $S'$ by (suitably many copies of) their averages, $\max S$ cannot increase! So imagine if we start replacing $(a_1,a_2)\rightarrow \left(\frac{a_1+a_2}{2},\frac{a_1+a_2}{2}\right)$, $p_1+p_2\rightarrow \frac{(a_1+a_2)^2}{2}$ (which is the smaller cases $n=2$!) and $p_k$ decreases for all $k\ge 3$.

If we be slightly greedier we can replace all of $a_1,...,a_{n-1}$ by their average $\overline{a}$ (and assume the truth for the $n-1$ case), then by the above knowledge we still know that $RHS$ decreases. So we only have to solve a weighted two-variable case that looks like this: for $\lambda, \mu > 0$, $$(\lambda a_1 + \mu a_2)(\lambda b_1 + \mu b_2) \le (\lambda + \mu)(\lambda a_1b_1+ \mu\max\{a_1b_2,a_2b_1,a_2b_2\})$$ which is very similar to the vanilla $n=2$ case shown earlier.

Discussion. A few interesting points of note:

• The $n=2$ case seems like a very ``natural’’ inequality. Is there a way to solve this without splitting into cases?
• What actually is Chebyshev’s inequality? If you think about it, it is essentially randomized Rearrangement: if $a_1\le ...\le a_n$ and $b_1\le ... \le b_n$, then we have $$(a_1+...+a_n)(b_1+...+b_n) = n\mathbb{E}_{\sigma}[a_1b_{\sigma(1)} + ... + a_nb_{\sigma(n)}] \le a_1b_1+...+a_nb_n$$ Is there a (productive) reinterpretation of this problem as some kind of random thing?
• I actually envisioned an alternative method as follows: first we normalize $a_1+...+a_n = b_1+...+b_n=1$ (since they are invariant under scaling), then we expand: $$(a_1+...+a_n)(b_1+...+b_n) = \frac{1}{2}\left((a_1+...+a_n)^2 + (b_1+...+b_n)^2\right)$$ Then maybe some kind of ``term counting’’ argument can finish this up (a la ISL 2003 A6). But who knows.