MathDB

2

Part of 2018 Baltic Way

Problems(1)

A table with unbalanced column sums

Source: Baltic Way 2018, Problem 2

11/6/2018
A 100×100100 \times 100 table is given. For each k,1≤k≤100k, 1 \le k \le 100, the kk-th row of the table contains the numbers 1,2,…,k1,2,\dotsc,k in increasing order (from left to right) but not necessarily in consecutive cells; the remaining 100−k100-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 1919 times as large as the sum of the numbers in the other column.