|
|
 |
Условие
В таблице 2×n расставлены положительные числа так, что в каждом из n столбцов сумма двух чисел равна 1.
Докажите, что можно вычеркнуть по одному числу в каждом столбце так, чтобы в каждой строке сумма оставшихся чисел не превосходила n+1/4.
Решение
Пусть в верхней строке стоят числа a1, a2, ..., an. Переставив столбцы, можно считать, что a1 ≤ a2 ≤ ... ≤ an. Тогда в нижней строке стоят соответственно
b1 = 1 – a1, b2 = 1 – a2, ..., bn = 1 – an; ясно, что b1 ≥ b2 ≥ ... ≥ bn. Если a1 + a2 + ... + an ≤ n+1/4, то вычеркнем все числа нижней строки. Иначе найдём такой минимальный номер k, что a1 + a2 + ... + an > n+1/4, вычеркнем в верхней строке числа ak, ak+1, ..., an, а в нижней – b1, b2, ..., bk–1. По выбору k
a1 + ... + ak–1 ≤ n+1/4. Поскольку то и
