A $100 \times 100$ table is given. For each $k, 1 \le k \le 100$, the $k$-th row of the table contains the numbers $1,2,\dotsc,k$ in increasing order (from left to right) but not necessarily in consecutive cells; the remaining $100-k$ cells are filled with zeroes. Prove that there exist two columns such that the sum of the numbers in one of the columns is at least $19$ times as large as the sum of the numbers in the other column.
Problem
Source: Baltic Way 2018, Problem 2
Tags:
WallyWalrus
06.11.2018 22:33
For $i,j,k\in\{1,2,\dots,100\}$, denote $a_{i,j}$ the element situated in the $i$-th row and $j$-th column; $R(i,k)=\sum_{j=1}^ka_{i,j}$ (the sum of the first $k$ elements of the $i$-th row); $C_j=\sum_{i=1}^{100}a_{i,j}$ (the sum of the elements of the $j$-th column). The sum of the all elements of the matrix is: $S=\sum_{i=1}^{100}R(i,100)=\sum_{i=1}^{100}\dfrac{i(i+1)}{2}=$ $\dfrac{1}{2}\sum_{i=1}^{100}i^2+\dfrac{1}{2}\sum_{i=1}^{100}i=171700$. $C_1\le 100\cdot 1=100$. The sum of the elements of the first $k$ columns is: $S_k=\sum_{j=1}^kC_j=\sum_{i=1}^{100}R(i,k)$. $R(i,k)\le \begin{cases}\dfrac{i(i+1)}{2}\;\text{for}\;i<k;\\\dfrac{k(k+1)}{2}\;\text{for}\;i\ge k.\end{cases}$ In the general case: $S_k\le \dfrac{(k-1)k(k+1)}{6}+\dfrac{k(k+1)(101-k)}{2}=\dfrac{-k^3+150k^2+151k}{3}$. For $k=20$: $S_{20}\le 18340$. The sum of the last $80$ columns is: $T=S-S_{20}\ge 153360$. Results: Exists an integer value $p,\; 21\le p\le 100$ such that $\max_{21\le j\le100}C_j=C_p\ge \dfrac{T}{80}=1917$. The proportion between $C_p$ and $C_1$ is $\dfrac{C_p}{C_1}\ge \dfrac{1917}{100}>19$. Observation: $k=20$ was just an example. Using the variation of the expression $\dfrac{S-S_k}{100-k}$ (or the calculator), results the property $\dfrac{S-S_k}{100-k}>1900$ for all $17\le k\le 33$.