# $10$ by $10$ board problem

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

• how do you place the numbers, in any order? – ILikeMath Sep 1 '13 at 17:14
• No, just randomly. – Matheo Sep 1 '13 at 17:16
• 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. – Kieran Cooney Sep 1 '13 at 18:48
• How did you get to the counter example? Could you explain further? – Matheo Sep 1 '13 at 19:16
• @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? – 6005 Sep 1 '13 at 20:47

## 1 Answer

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.

• 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. – Brian M. Scott Sep 1 '13 at 20:52
• 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). – user84413 Sep 1 '13 at 23:51
• I'm unsure; there's several aspects things that would scale, but it's unclear whether they would overall scale favourably. – Rebecca J. Stones Sep 2 '13 at 0:07
• 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/… – Help - I need somebody's help Sep 2 '13 at 10:39
• Very nice! Quite similar to mine. – Matheo Sep 6 '13 at 12:22