Олимпиадная задача Куликова: 2×n таблица, неравенства, 8

Задача

В таблице 2×n расставлены положительные числа так, что в каждом из n столбцов сумма двух чисел равна 1.

Докажите, что можно вычеркнуть по одному числу в каждом столбце так, чтобы в каждой строке сумма оставшихся чисел не превосходила ⁿ⁺¹/₄.

Решение

Пусть в верхней строке стоят числа a₁, a₂, ..., a_n. Переставив столбцы, можно считать, что a₁ ≤ a₂ ≤ ... ≤ a_n. Тогда в нижней строке стоят соответственно

b₁ = 1 – a₁, b₂ = 1 – a₂, ..., b_n = 1 – a_n; ясно, что b₁ ≥ b₂ ≥ ... ≥ b_n. Если a₁ + a₂ + ... + a_n ≤ ⁿ⁺¹/₄, то вычеркнем все числа нижней строки. Иначе найдём такой минимальный номер k, что a₁ + a₂ + ... + a_n > ⁿ⁺¹/₄, вычеркнем в верхней строке числа a_k, a_k+1, ..., a_n, а в нижней – b₁, b₂, ..., b_k–1. По выбору k