7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ how do you place the numbers, in any order? $\endgroup$ – ILikeMath Sep 1 '13 at 17:14
  • $\begingroup$ No, just randomly. $\endgroup$ – Matheo Sep 1 '13 at 17:16
  • 2
    $\begingroup$ Do you mean to include columns as well as rows? By putting the numbers 1 to 100 in the square in order theschools.com/theschools/curriculum/samplelessons/Graphics/2/… and then flipping them about the 1-100 diagonal, we get a counter example. $\endgroup$ – Kieran Cooney Sep 1 '13 at 18:48
  • 1
    $\begingroup$ How did you get to the counter example? Could you explain further? $\endgroup$ – Matheo Sep 1 '13 at 19:16
  • 1
    $\begingroup$ @KieranCooney I think that is not a counterexample. The rows will be (1,11,21,...,91), (2,12,22,..,92), and so on, so $S$ will be $71 + 72 + 73 + \cdots + 80$. The first row has a sum less than $S$ because $1 + 11 + \cdots + 91 < 71 + 72 + \cdots + 80$. What am I missing? $\endgroup$ – 6005 Sep 1 '13 at 20:47
11
$\begingroup$

Without loss of generality, we can reorder the contents of each row. Thus, we can assume that $x_{i(j-1)}<x_{ij}$ for $1 \leq j \leq 9$. So the third greatest entry in each cell is in the column indexed by $7$. Without loss of generality, we can permute the rows so that $x_{(i-1)7}<x_{i7}$ whenever $1 \leq i \leq 9$.

So the matrix is: $$\begin{pmatrix} x_{00} & x_{01} & x_{02} & x_{03} & x_{04} & x_{05} & x_{06} & \mathbf{x_{07}} & x_{08} & x_{09} \\ x_{10} & x_{11} & x_{12} & x_{13} & x_{14} & x_{15} & x_{16} & \mathbf{x_{17}} & x_{18} & x_{19} \\ x_{20} & x_{21} & x_{22} & x_{23} & x_{24} & x_{25} & x_{26} & \mathbf{x_{27}} & x_{28} & x_{29} \\ x_{30} & x_{31} & x_{32} & x_{33} & x_{34} & x_{35} & x_{36} & \mathbf{x_{37}} & x_{38} & x_{39} \\ x_{40} & x_{41} & x_{42} & x_{43} & x_{44} & x_{45} & x_{46} & \mathbf{x_{47}} & x_{48} & x_{49} \\ x_{50} & x_{51} & x_{52} & x_{53} & x_{54} & x_{55} & x_{56} & \mathbf{x_{57}} & x_{58} & x_{59} \\ x_{60} & x_{61} & x_{62} & x_{63} & x_{64} & x_{65} & x_{66} & \mathbf{x_{67}} & x_{68} & x_{69} \\ x_{70} & x_{71} & x_{72} & x_{73} & x_{74} & x_{75} & x_{76} & \mathbf{x_{77}} & x_{78} & x_{79} \\ x_{80} & x_{81} & x_{82} & x_{83} & x_{84} & x_{85} & x_{86} & \mathbf{x_{87}} & x_{88} & x_{89} \\ x_{90} & x_{91} & x_{92} & x_{93} & x_{94} & x_{95} & x_{96} & \mathbf{x_{97}} & x_{98} & x_{99} \\ \end{pmatrix}$$

Let $M_i$ be the submatrix formed by the intersection of the rows $\{0,1,\ldots,i\}$ and columns $\{0,1,\ldots,7\}$. The number $\mathbf{x_{i7}}$ is the maximum number in $M_i$. Hence $\mathbf{x_{i7}} \geq 8(i+1)$ and so $$S \geq \sum_{i=0}^9 8(i+1)=440.$$

Let $m$ be the minimum row sum.

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}}$.) Hence summing rows $0,\ldots,i$ yields $$(i+1)m \leq 8(i+1) \mathbf{x_{i7}}-\left(\sum_{k=1}^{8(i+1)-1} k\right)+100+99+\cdots+(100-2i-1).$$ This implies $m<440$ (and we are done) if any of the following are true: \begin{align*} \mathbf{x_{07}} \leq 33, \\ \mathbf{x_{17}} \leq 37, \\ \mathbf{x_{27}} \leq 42, \\ \mathbf{x_{37}} \leq 46, \\ \mathbf{x_{47}} \leq 50, \\ \mathbf{x_{57}} \leq 54, \\ \mathbf{x_{67}} \leq 59, \\ \mathbf{x_{77}} \leq 63, \\ \mathbf{x_{87}} \leq 67, \\ \mathbf{x_{97}} \leq 71. \\ \end{align*} Now assume all of the above are false. Then $$S \geq 34+38+43+47+51+55+60+64+68+72 = 532.$$ Since the average row sum is $\frac{1}{10}\sum_{i=1}^{100}i=505$, $$m \leq 505 < S$$ and we are done.

$\endgroup$
  • 2
    $\begingroup$ Very nice! I took the liberty of changing the index variable in two sums from $i$ to $k$: you were already using $i$ as a constant in those sums. $\endgroup$ – Brian M. Scott Sep 1 '13 at 20:52
  • $\begingroup$ Nice answer! You don't have to respond to this, but I am curious if this method will work for other size boards besides 10x10 (or if there's something special about 10). $\endgroup$ – user84413 Sep 1 '13 at 23:51
  • $\begingroup$ I'm unsure; there's several aspects things that would scale, but it's unclear whether they would overall scale favourably. $\endgroup$ – Rebecca J. Stones Sep 2 '13 at 0:07
  • 1
    $\begingroup$ I'm having a bit of trouble understanding this.. It will be great if someone can answer my question regarding computing the biggest possible value for $M_i$: math.stackexchange.com/questions/481981/… $\endgroup$ – Help - I need somebody's help Sep 2 '13 at 10:39
  • $\begingroup$ Very nice! Quite similar to mine. $\endgroup$ – Matheo Sep 6 '13 at 12:22

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.