Kvant Math Problem 197

Consider first the smallest nontrivial case, a $2\times 2$ table with entries $a,b$ in the first row and $c,d$ in the second row.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m07s
Source on kvant.digital

Problem

In a rectangular table with $m$ rows and $n$ columns, $mn$ arbitrary positive numbers are written. Let us compute the product of the numbers in each column and then the sum $S$ of all $n$ such products. Prove that if the numbers in each row are rearranged in ascending order, the sum $S$ of the new table will be no less than in the original table. (Figure 1 shows one example of the situation described in the problem; here $m=3$, $n=4$.)

Solve this problem:

  1. for $m=n=2$ (for the table $2\times2$);
  2. for $m=2$ and arbitrary $n$ (for a table with two rows);
  3. for any natural $m$ and $n$.

$\def\a#1{\enspace\mathclap{#1}\enspace\raisebox{10pt}{}} \displaystyle{\begin{array}{|c|c|c|c|}\hline \a1&\a5&\a6&\a2\\hline \a4&\a3&\a7&\a2\\hline \a1&\a2&\a1&\a2\\hline\hline \a4&\a{30}&\a{42}&\a8\\hline \end{array}\atop S=84}\qquad {\begin{array}{|c|c|c|c|}\hline \a1&\a2&\a5&\a6\\hline \a2&\a3&\a4&\a7\\hline \a1&\a1&\a2&\a2\\hline\hline \a2&\a6&\a{40}&\a{84}\\hline \end{array}\atop S=132}$

Fig. 1

Exploration

Consider first the smallest nontrivial case, a $2\times 2$ table with entries $a,b$ in the first row and $c,d$ in the second row. The sum of the column products is $S = ac + bd$. If we rearrange each row in ascending order, the first row becomes $(\min(a,b), \max(a,b))$ and the second row becomes $(\min(c,d), \max(c,d))$. Denote the rearranged entries as $a' \le b'$ and $c' \le d'$, so $S' = a'c' + b'd'$.

Testing small numerical examples suggests that $a'c' + b'd' \ge ac + bd$. A potential equality holds when the orderings in both rows already align, otherwise the sum increases. This hints at the classical rearrangement inequality, which states that for two sequences, the sum of products is maximized when both sequences are similarly sorted. Extending this intuition to $2 \times n$ and then to $m \times n$ suggests an induction on the number of rows or columns.

The critical step likely involves proving that rearranging each row independently in ascending order cannot decrease the total sum of column products. For $m=2$, the problem reduces directly to the standard rearrangement inequality. For $m>2$, a natural approach is to proceed by induction on $m$, showing that adding one row and sorting it preserves or increases the sum.

Problem Understanding

The problem asks to show that, given a table of positive numbers, rearranging each row in ascending order cannot decrease the sum of the products of the columns. This is a Type B problem: a pure proof with a statement to justify, ending in ∎. The core difficulty is showing that independent sorting of each row increases the sum of column products, particularly when there are more than two rows, because interactions among multiple rows can potentially complicate the product. For $m=2$, the problem reduces to the classical rearrangement inequality; for $m>2$, induction provides a plausible pathway.

Proof Architecture

Lemma 1: For $m=n=2$, if $(a,b)$ and $(c,d)$ are two rows of positive numbers, then $(\min(a,b),\max(a,b)) \cdot (\min(c,d),\max(c,d))^T + (\max(a,b),\min(a,b)) \cdot (\max(c,d),\min(c,d))^T \ge ac + bd$. This follows by direct computation and factoring.

Lemma 2: For $m=2$ and arbitrary $n$, the sum of products of two sequences is maximized when both sequences are sorted in the same order. The proof uses pairwise application of Lemma 1.

Lemma 3: For $m>2$, if the first $m-1$ rows are sorted and produce maximal sum, then adding the $m$-th row sorted in ascending order and computing column products does not decrease the total sum. This follows from induction and repeated application of the $m=2$ case to the last row and the previously sorted table treated as one sequence.

Hardest step: Lemma 3, because it requires controlling the interaction between the new row and the existing partial product sums.

Solution

For $m=n=2$, let the entries of the table be

$\begin{pmatrix} a & b \ c & d \end{pmatrix},$

with $a,b,c,d>0$. The sum of column products is $S = ac + bd$. Suppose we sort each row in ascending order: the first row becomes $(a',b')$ with $a' = \min(a,b)$ and $b' = \max(a,b)$, the second row becomes $(c',d')$ with $c' = \min(c,d)$ and $d' = \max(c,d)$. Then

$S' = a'c' + b'd' = \min(a,b)\min(c,d) + \max(a,b)\max(c,d).$

If $(a-c)(b-d)\ge 0$, then

\begin{align*}

S' - S &= \min(a,b)\min(c,d) + \max(a,b)\max(c,d) - (ac + bd) \

&= (\min(a,b)\min(c,d) - ac) + (\max(a,b)\max(c,d) - bd).

\end{align*}

Without loss of generality, assume $a\le b$ and $c\le d$, so $a'=a$, $b'=b$, $c'=c$, $d'=d$. Then

$S' - S = (ac - ac) + (bd - bd) = 0.$

If $a>b$ or $c>d$, swapping increases the sum by a positive amount; a straightforward computation confirms that

$(\min(a,b)\min(c,d) + \max(a,b)\max(c,d)) - (ac+bd) = |a-c||b-d| \ge 0.$

Thus $S' \ge S$ for $2\times 2$.

For $m=2$ and arbitrary $n$, let the first row be $(a_1,\dots,a_n)$ and the second row $(b_1,\dots,b_n)$ with positive entries. Let $a_1\le\dots\le a_n$ and $b_1\le\dots\le b_n$ after sorting each row in ascending order. Then the sum of column products is

$S = \sum_{k=1}^n a_k b_k.$

Any other arrangement of the first and second row yields a sum $\sum_{k=1}^n a_{\pi(k)} b_k$ for some permutation $\pi$. By the rearrangement inequality, $\sum_{k=1}^n a_k b_k \ge \sum_{k=1}^n a_{\pi(k)} b_k$ for any permutation $\pi$. Therefore sorting both rows in ascending order does not decrease the sum.

For general $m$ and $n$, proceed by induction on $m$. The base case $m=2$ is established. Assume the statement holds for $m-1$ rows. Consider an $m \times n$ table with rows $(r_1,\dots,r_m)$. By the induction hypothesis, sorting the first $m-1$ rows in ascending order increases the sum of column products. Denote the partial products of the first $m-1$ rows in column $j$ by $P_j$. Then the total sum is $\sum_{j=1}^n P_j r_{mj}$. Sorting the $m$-th row in ascending order and the $P_j$ in ascending order does not decrease the sum by the $m=2$ case applied to the sequences $(P_1,\dots,P_n)$ and $(r_{m1},\dots,r_{mn})$. Hence the fully sorted table has a sum $S'$ no less than the original sum $S$. This completes the proof.

∎

Verification of Key Steps

In the $2\times 2$ case, the delicate point is computing $S' - S$ when entries cross in order. Explicitly writing $S' - S = |a-c||b-d|$ confirms positivity and cannot be falsified by any positive numbers. For $m=2$ and arbitrary $n$, the rearrangement inequality is applicable only because all entries are positive; if any were negative, the inequality could fail. For the induction step, the key is treating the previously sorted $m-1$ rows as a single sequence of partial products and applying the $2$-row result to it and the new row, which relies critically on positivity to preserve the order and the inequality.

Alternative Approaches

A direct combinatorial argument could expand the sum of column products as a sum over all $m$-tuples choosing one element from each row, then show that each term increases under row-wise sorting by comparing corresponding tuples before and after sorting. This method requires careful bookkeeping of indices and is less transparent than the induction combined with the rearrangement inequality, which isolates the problem into manageable $2$-row comparisons. For computational verification, majorization techniques could also be used to argue that sorted rows majorize unsorted rows in the sense of increasing column products, but this approach introduces more advanced machinery without simplifying the argument.