Skip to main content
OlympiadHQ

Browse · MathNet

Print

Baltic Way shortlist

Baltic Way counting and probability

Problem

Non-negative integers are written in some cells of table. For each , , the -th row of the table contains numbers from to written in increasing order (from left to right) but not necessarily in consecutive cells. The empty cells are filled with zeroes. Prove that there exist two columns such that the sum of numbers in one of them is at least times greater than the sum in the second column.
Solution
Observe that the sum of numbers in the first column is at most , the sum in the first and second columns is at most , the sum in the first, second and third columns is at most , etc. But the sum of all nonzero numbers equals , therefore the sum in the columns from -th to -th is at least Therefore one of these columns has a sum at least . Therefore the ratio of sums in this column and in the first one is more than .

Techniques

Pigeonhole principleColoring schemes, extremal argumentsSums and products