# Having trouble understanding the solution for the 10x10 board problem

The original question was posted by Matheo:

We place the numbers 1,2,...,100 on the 100 squares of a 10 by 10 board. We then take the third greatest number from each row and create their sum S. Prove that at least one row has a sum of numbers that is less than S.

and was answer by Rebecca.

I understood half of it. But at this part it starts to look confusing:

The sum of the entries of $M_i$ must be at most $$8(i+1) \mathbf{x_{i7}}-\left(\sum_{k=1}^{8(i+1)-1} k\right).$$ (The maximum is achieved when the numbers in $M_i$ are the $8(i+1)$ largest integers not exceeding $\mathbf{x_{i7}}$.)

I'm not a really bright person.. So I would like to know why in order to compute the biggest possible value for $M_i$, we need to first

$$8(i+1) \mathbf{x_{i7}}$$

What is the reason behind multiplying $8(i+1)$, which is $\mathbf{x_{i7}}$'s smallest possible value, with $\mathbf{x_{i7}}$?

And how is the maximum achieved when the numbers in $M_i$ are the $8(i+1)$ largest integers not exceeding $\mathbf{x_{i7}}$?

What does it mean by being "the $8(i+1)$ largest integers but smaller than $\mathbf{x_{i7}}$"?

• The reason for multiplying $\mathbf{x_{i7}}$ with $8(i+1)$ is that the matrix $M_i$ contains $8(i+1)$ elements. – Daniel Fischer Sep 2 '13 at 11:11

## 1 Answer

It's true for any integer matrix $M=(m_{ij})_{m \times n}$ without repeated numbers. The sum of the entries of $M$ is at most $$nm\max(M)-\sum_{k=1}^{nm-1} k.$$ In the particular matrix in the earlier question, it was an $8 \times (i+1)$ matrix with maximum $\mathbf{x}_{i7}$.

Let's use this as a running example: $$M=\begin{array}{|ccccc|} \hline 12 & 30 & 36 & 7 & 34 \\ 24 & 38 & 25 & 6 & 28 \\ 20 & 32 & -5 & 37 & 0 \\ \hline \end{array}.$$

• Let $X=(x_{ij})_{m \times n}$ be the matrix defined by $x_{ij}=\max(M)$.

So, in our example $\max(M)=38$ and so $$X=\begin{array}{|ccccc|} \hline 38 & 38 & 38 & 38 & 38 \\ 38 & 38 & 38 & 38 & 38 \\ 38 & 38 & 38 & 38 & 38 \\ \hline \end{array}.$$

• Let $D=(d_{ij})_{m \times n}$ be defined by $D=X-M$.

So, in our example $$D=\begin{array}{|ccccc|} \hline 26 & 8 & 2 & 31 & 4 \\ 14 & 0 & 13 & 32 & 10 \\ 18 & 6 & 43 & 1 & 38 \\ \hline \end{array}.$$

We have defined $X$ and $D$ such that $M=X-D$. So the sum of entries in $M$ is the sum of entries in $X$ minus the sum of entries in $D$.

By definition, the sum of entries in $X$ is $nm\max(M)$.

The matrix $D$ contains $0$ and $nm-1$ distinct positive integers. The smallest possible sum of $nm-1$ distinct positive integers is $\sum_{k=1}^{nm-1} k$ (which are the $nm-1$ smallest positive integers). Hence the sum of entries in $M$ is at most $$nm\max(M)-\sum_{k=1}^{nm-1} k.$$ (We could make this last step formal by creating a sorted list from the entries of $D$ and showing each element is no smaller than the corresponding element in the sequence $(0,1,\ldots,nm-1)$.)