4
$\begingroup$

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}}$"?

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

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)$.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.