$10$ $10$ problema en la placa

Question

Ponemos los números de $1,2,...,100$ $100$ plazas de una $10$ $10$ junta. A continuación, tomamos la tercera mayor número de cada fila y crear su suma $S$. Demostrar que al menos una fila tiene una suma de números que está a menos de $S$.

Answer 1

Sin pérdida de generalidad, podemos reordenar el contenido de cada fila. Por lo tanto, podemos asumir que $x_{i(j-1)}<x_{ij}$$1 \leq j \leq 9$. Entonces, la tercera más grande de la entrada en cada celda en la columna indizada por $7$. Sin pérdida de generalidad, podemos permutar las filas de modo que $x_{(i-1)7}<x_{i7}$ siempre $1 \leq i \leq 9$.

Por lo que la matriz es: $$\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}$$

Deje $M_i$ ser la submatriz formada por la intersección de las filas $\{0,1,\ldots,i\}$ y columnas $\{0,1,\ldots,7\}$. El número de $\mathbf{x_{i7}}$ es la cantidad máxima en $M_i$. Por lo tanto $\mathbf{x_{i7}} \geq 8(i+1)$ $$S \geq \sum_{i=0}^9 8(i+1)=440.$$

Deje $m$ ser el mínimo de fila suma.

La suma de las entradas de $M_i$ debe ser en la mayoría de los $$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,me$ 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$ (y se hacen) si cualquiera de los siguientes son verdaderas: $$\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*}$$ Ahora asumir todas las anteriores son falsas. Entonces $$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$$ y hemos terminado.