2
$\begingroup$

$0.7<2.4,\ $ and $\ 0.8< 0.9.$ By calculation, we see that $0.7\times 0.8 + 2.4\times 0.9 > 0.7\times 0.9 + 2.4\times 0.8.$

Indeed, for any pair of two numbers $\ 0<a<b\ $ and $\ 0<c<d,\ $ we have $\ (b-a)d>(b-a)c,$ and so $\ bd+ac>bc+ad.\quad (1)$

Can this inequality be generalised to include more than just two lots of two numbers? Let me elaborate.

Suppose we have an array of positive real numbers, where each row is ordered from largest to smallest:

$$ \begin{array}{} a_{11} & > &a_{12} & > & \ldots & > & a_{1n}\\ a_{21} & > &a_{22} & > & \ldots & > & a_{2n}\\ \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ a_{k1} & > &a_{k2} & > & \ldots & > & a_{kn}\\ \end{array} $$

We choose one entry from each row, multiply these numbers together, remove them from the above array, then repeat this process. For example, if $\ n=3\ $ and $\ k=4,\ $ one possible outcome could be:

$$a_{11}\times a_{23}\times a_{31}\times a_{42} + a_{12}\times a_{21}\times a_{32}\times a_{41} + a_{13}\times a_{22}\times a_{33}\times a_{43}\quad (2)$$

where $\ \times$ just means standard multiplication.

$(2)\ $ is one way of choosing the sum of the products if $\ n=3\ $ and $\ k=4.$ Indeed, there are many ways to choose the sum of products [the number of permutations could be an interesting combinatorics problem, but that is for another day...].

Now, I suspect the permutation [way of choosing the sum of products] that yields the largest value is:

$$ a_{11}\times a_{21}\times\ldots\times a_{k1}\ +\ a_{12}\times a_{22}\times\ldots\times a_{k2}\ + \ldots\ +\ a_{1n}\times a_{2n}\times\ldots\times a_{kn}.\quad (3) $$

Certainly, if we swap two entries in the above, for example, to get:

$$ a_{11}\times a_{2n}\times\ldots\times a_{k1}\ +\ a_{12}\times a_{22}\times\ldots\times a_{k2}\ + \ldots\ +\ a_{1n}\times a_{21}\times\ldots\times a_{kn}.\quad (4)$$

then $\ (4)\ $ will be less than $\ (3)\ $ because of the result $\ (1).$ But for two or more swaps, I think it will become either messy or simply not possible to use $\ (1)\ $ in a proof.

I was thinking Cauchy- Schwarz might be relevant, but I'm not sure. But yeah, I'm not sure if the result is true and if it is, how to go about proving it.

$\endgroup$
2
  • 2
    $\begingroup$ The $k = 2$ case is simply the rearrangement inequality, and I suspect the general case would be easy to prove by induction. $\endgroup$ Commented Jul 28, 2021 at 15:55
  • $\begingroup$ @ Connor Harris Thank you- I wasn’t aware of that inequality. $\endgroup$ Commented Jul 28, 2021 at 15:57

0

You must log in to answer this question.