Each square of a chessboard contains a number. The sum of the two largest numbers in each row is the same. The sum of the two largest numbers in each column is also the same. What is the maximum possible difference between the two sums?

Sunday, February 12, 2012

Please email your solutions to puzzles@cotpi.com.

### 3 comments

### Credit

This puzzle is taken from:

- Khovanova, Tanya. "Moscow Math Olympiad." Tanya Khovanova’s Math Blog. 2 June 2011. 12 Feb. 2012 <http://blog.tanyakhovanova.com/?p=338>.

## Hagen von Eitzen solved this puzzle:

The answer is 0, which follows from theorem 1 below. \( \newcommand{\setn}{I} \def\myA#1{a_{#1}} \def\myAA#1{a'_{#1}} \)

Consider a real \(n \times n\) matrix \(A = (\myA{i,j})_{i,j=1}^n\) with \(n \ge 2\). Define \(\setn= \{1, \dots, n\}\) as a shorthand for the index set. For each row index \(i \in \setn\), let \(\alpha(i)\) denote the column index of the largest entry and \(\beta(i)\) the column index of the second-largest entry of the \(i\)th row of \(A\). That is, for all \(i\in\setn\) we have

\begin{align} & \alpha(i) \ne \beta(i), \label{abDiff} \\ & \myA{i, \alpha(i)} \ge \myA{i, \beta(i)} \text{ and} \label{aGTb} \\ & \text{if } j \in \setn \text{ with } \myA{i,j} > \myA{i, \beta(i)} \text{ then } j = \alpha(i). \label{abOther} \end{align}

Similary, for each column index \(j \in \setn\), let \(\gamma(i)\) denote the row index of the largest entry and \(\delta(i)\) the row index of the second-largest entry of the \(j\)th column. That is, for all \(j \in \setn\) we have

\begin{align} & \gamma(j) \ne \delta(j), \label{cdDiff} \\ & \myA{\gamma(j), j} \ge \myA{\delta(j), j} \text{ and} \label{cGTd} \\ & \text{if } i \in \setn \text{ with } \myA{i,j} > \myA{\delta(j), j} \text{ then } i = \gamma(j). \label{cdOther} \end{align}

Lemma 1.Let \(A\) be a real \(n\times n\) matrix and \(r, c\) be real numbers with \(r < c\) such that with the above definitions \(\myA{i, \alpha(i)} + \myA{i, \beta(i)} = r\) for all \(i \in \setn\) and \(\myA{\gamma(j), j} + \myA{\delta(j), j} = c\) for all \(j \in \setn\). Then the maps \(\alpha \colon \setn \to \setn\) and \(\gamma \colon \setn \to \setn\) are inverses of each other.Proof.Assume that \(\gamma(\alpha(i)) \ne i\) for some \(i \in \setn\). Then \(\myA{\gamma(\alpha(i)), \alpha(i)} \ge \myA{\delta(\alpha(i)), \alpha(i)}\) from \eqref{cGTd}, \(\myA{\delta(\alpha(i)), \alpha(i)} \ge \myA{i,\alpha(i)}\) from \eqref{cdOther} using \(i \ne \gamma(\alpha(i))\), and \(\myA{i, \alpha(i)} \ge \myA{i, \beta(i)}\) from \eqref{aGTb}. Combined this yields \[ c = \myA{\gamma(\alpha(i)), \alpha(i)} + \myA{\delta(\alpha(i)), \alpha(i)} \ge \myA{i, \alpha(i)} + \myA{i, \beta(i)} = r, \] contradicting \(r > c\). Therefore, for all \(i \in \setn\) we have \(\gamma(\alpha(i)) = i\). This makes \(\alpha \colon \setn \to \setn\) an injective, hence bijective mapping and \(\gamma\) its inverse.Lemma 2.Under the conditions stated in lemma 1, row and column maxima are strict, i.e. we have \(\myA{i, \alpha(i)} \gt \myA{i, \beta(i)}\) for all \(i \in \setn\) and \(\myA{\gamma(i),j} \gt \myA{\delta(i), j}\) for all \(j \in \setn\).Proof.Assume that \(\myA{i, \alpha(i)} \le \myA{i, \beta(i)}\) for some \(i \in \setn\). Then \(\myA{i, \alpha(i)} =\myA{i, \beta(i)}\) because of \eqref{aGTb}. If we swap \(\alpha(i) \leftrightarrow \beta(i)\), statements \eqref{abDiff}, \eqref{aGTb} and \eqref{abOther} remain valid, hence by lemma 1 both this modified \(\alpha\) and the original \(\alpha\) are inverse of \(\gamma\), a contradiction.Assume that \(\myA{\gamma(j), j} \le \myA{\delta(j), j}\) for some \(j \in \setn\). Then \(\myA{\gamma(j), j} = \myA{\delta(j), j}\) because of \eqref{cGTd}. If we swap \(\gamma(i) \leftrightarrow \delta(i)\), statements \eqref{cdDiff}, \eqref{cGTd} and \eqref{cdOther} remain valid, hence again lemma 1 shows that both this modified \(\gamma\) and the original \(\gamma\) are inverses of \(\alpha\), a contradiction.

Theorem 1.Let \(A\) be an \(n \times n\) real matrix and \(r, c\) be real numbers such that with the above definitions \(\myA{i, \alpha(i)} + \myA{i, \beta(i)} = r\) for all \(i \in \setn\) and \(\myA{\gamma(j), j} + \myA{\delta(j), j} = c\) for all \(j \in \setn\). Then \(r = c\).Proof.Assume on the contrary that \(r \ne c\). Without loss of generality, \(r \gt c\) (else we can replace \(A\) with \(A^T\) and swap \(\alpha \leftrightarrow \gamma\), \(\beta \leftrightarrow \delta\) and \(r \leftrightarrow c\)).Let \(h_1 = \min\bigl( \{ |\myA{i, \alpha(i)} - \myA{i, \beta(i)}| \mid i \in \setn \} \bigr) \), \(h_2 = \min\bigl( \{ |\myA{\gamma(j), j} - \myA{\delta(j), j}| \mid j \in \setn \} \bigr) \) and \(h = \min\{ h_1, h_2 \}\). By lemma 2, \(h > 0\). Define the matrix \(A' = (\myAA{i, j})_{i,j=1}^n\) by setting

\[ \myAA{i,j} = \begin{cases} \myA{i, j} - h & \text{if } j = \alpha(i)\\ \myA{i, j} & \text{otherwise}. \end{cases} \]

According to lemma 1, this is equivalent to

\[ \myAA{i, j} = \begin{cases} \myA{i, j} -h & \text{if } i=\gamma(j)\\ \myA{i, j} & \text{otherwise}. \end{cases} \]

By these choices, statements (1) through (6) remain valid if one replaces \(A\) with \(A'\). Moreover, \(\myAA{i, \alpha(i)} + \myAA{i, \beta(i)} = r - h\) for all \(i \in \setn\) and \(\myAA{\gamma(j), j} + \myAA{\delta(j), j)} = c - h\) for all \(j \in \setn\). Therefore the conditions of lemma 1 and lemma 2 apply to \(A'\) with \(r - h, c - h\) instead of \(r, c\). If \(h = h_1\), we have \(\myAA{i, \alpha(i)} = \myAA{i, \beta(i)}\) for some \(i \in \setn\), and if \(h = h_2\), we have \(\myAA{\gamma(j),j}=\myAA{\delta(j),j}\) for some \(j\in\setn\). In both cases, we arrive at a contradiction to the result of lemma 2.

## James Dow Allen solved this puzzle:

Zero.

We prove the stronger result that in any \(n \times n\) matrix, if the two largest numbers in each column sum to a constant, then some row has a pair of numbers that sum to at least as much.

That result is true for any \(2 \times 2\) matrix. We will assume the result to be true for any \((n - 1) \times (n - 1)\) matrix.

Suppose there is an \(n \times n\) counterexample, i.e. a matrix with the two largest numbers in each column that sum to \(k\), but no row with a pair of numbers with a sum greater than \(k - 1\).

Let the largest number in the matrix be \(v\). Permute its rows and columns so that \(v\) is in the bottom-right corner. The bottom row has no element greater than \(k - v - 1\) since no row has a pair of numbers with a sum greater than \(k - 1\).

If a value in the bottom row except \(v\) is one of the two largest numbers in its column, then there must be another number greater than or equal to \(v + 1\) in the same column so that their sum is \(k\). But this is a contradiction since \(v\) is the largest number in the matrix. So, none of the numbers in the bottom row except \(v\) can be one of the two largest numbers in its column.

So, the largest two numbers in each column of the \((n - 1) \times (n - 1)\) matrix obtained by omitting the last row and column also sum to \(k\). Thus, by our hypothesis, some row of the \((n - 1) \times (n - 1)\) matrix has a pair of numbers that has a sum greater than or equal to k, and so does the corresponding row of the \(n \times n\) matrix. This is a contradiction.

Similarly, we can prove that in any \(n \times n\) matrix, if the two largest numbers in each row sum to a constant, then some column has a pair of numbers that sum to at least as much.

Thus, in any \(n \times n\) matrix, if the two largest numbers in each row sum to a constant, and the two largest numbers in each column sum to a constant, then the two constants must be equal.

## Susam Pal from cotpi added:

Here is another way to show that the sum of the two largest numbers in any row of the chessboard is equal to the sum of the two largest numbers in any column of the chessboard.

Theorem.In an \(n \times n\) matrix of real numbers where \(n \geqslant 2\), if the sum of the two largest numbers in each row is \(a\) and the sum of the two largest numbers in each column is \(b\), then \(a = b\).Proof.Without loss of generality, let us assume \(a \gt b\). Let \(M_i\) and \(m_i\) be the two largest numbers in the \(i\)th row such that \(M_i \geqslant m_i\) where \(1 \leqslant i \leqslant n\) is an integer. So, we get \(2 M_i \geqslant M_i + m_i = a\). Hence, \(M_i \geqslant \frac{a}{2}\).If there are two numbers \(M_i\) and \(M_j\) in the same column for integers \(i \ne j\) and \(1 \leqslant i \lt j \leqslant n\), then \(M_i + M_j \geqslant a \gt b\), a contradiction since the sum of the two largest numbers in any column is \(b\). So, every \(M_i\) for integers \(1 \leqslant i \leqslant n\) is in a different column.

Let \(x = \max\bigl( \{ m_i \mid i \in \mathbb{N} \text{ and } 1 \leqslant i \leqslant n \} \bigr)\). Let \(y \in \{M_i \mid i \in \mathbb{N} \text{ and } 1 \leqslant i \leqslant n \}\) such that \(y\) occurs in the same column as \(x\). Let \(z \in \{m_i \mid i \in \mathbb{N} \text{ and } 1 \leqslant i \leqslant n \}\) such that \(z\) occurs in the same row as \(y\). So, \(y \geqslant x \geqslant z\), \(x + y = b\) and \(y + z = a\). Since \(x \geqslant z\), \(x + y \geqslant y + z\) and thus \(b \geqslant a\). This is a contradiction to our assumption that \(a \gt b\). Hence, \(a = b\).