Indija TS 2012

Question

Suppose 2n real numbers are placed in the cells of a 2 n grid such that the sum of the numbers in each of the n columns is 1. Prove that one can erase one of the two numbers in each column such that the sum of the remaining numbers in each of the rows does not exceed n+14.

Accepted Answer

Assume that the numbers in the first row are a_1 a_2 a_n in some order. The numbers in the second row are b_j = 1 - a_j, 1 j n. Hence b_1 b_2 b_n. If a_1 + a_2 + + a_n n+14, we are done (we can erase all the numbers in the second row). Let k be the least positive integer such that a_1 + a_2 + + a_k > n+14. Then a_1 + a_2 + + a_k-1 n+14. We show that b_k + b_k+1 + + b_n n+14. Observe a_k a_1 + a_2 + + a_kk > n+14k. Hence b_k + b_k+1 + + b_n (n+1-k)b_k = (n+1-k)(1-a_k) < (n+1-k) (1 - n+14k) = 54(n+1) - ((n+1)^2 + 4k^24k) (AM-GM) 54(n+1) - 2(n+1)(2k)4k = n+14.