Разделы 
Дополнительно
Задача по математике - 2038
2019-01-23 
В таблице $2 \times n$ расставлены положительные числа так, что в каждом из $n$ столбцов сумма двух чисел равна 1. Докажите, что можно вычеркнуть по одному числу в каждом столбце так, чтобы в каждой строке сумма оставшихся чисел не превосходила $\frac{n + 1}{4}$.
Решение:
Пусть в верхней строке стоят числа $a_1, a_2, \cdots, a_n$. Переставим столбцы так, что $a_1 \leq a_2 \leq \cdots \leq a_n$. Тогда в нижней строке стоят соответственно $b_1 = 1 - a_1, b_2 = 1 - a_2, \cdots, b_n = 1 - a_n$; ясно, что $b_1 \geq b_2 \cdots b_n$. Если $a_1 + a_2 + \cdots + a_n \leq \frac{n+1}{4}$, то вычеркнем все числа нижней строки. Иначе найдем минимальный номер $k$ такой, что $a_1 + a_2 + \cdots + a_k > \frac{n+1}{4}$, вычеркнем в верхней строке числа $a_k, a_{k+1}, \cdots, a_n$, а в нижней - $b_1, b_2,\cdots, b_{k-1}$. По выбору $к$ имеем $a_1 + \cdots + a_{k-1} \leq \frac{n+1}{4}$. Остается доказать, что $b_k + b_{к+1} + \cdots + b_n \leq \frac{n+1}{4}$.
Поскольку $a_k \geq \frac{a_1+ \cdots + a_k}{k} > \frac{n+1}{4k}$, имеем
$b_k + b_{k+1} + \cdots + b_n \leq (n+1 - k)b_k = (n+1 -k)(1-a_k) < (n+1-k)(1- \frac{n+1}{4k}) = \frac{5}{4}(n+1) - [\frac{(n+1)^2 + (2k)^2}{4k}] \leq \frac{5}{4}(n+1) - \frac{2(n+1)(2k)}{4k} = \frac{n+1}{4}$.
В таблице $2 \times n$ расставлены положительные числа так, что в каждом из $n$ столбцов сумма двух чисел равна 1. Докажите, что можно вычеркнуть по одному числу в каждом столбце так, чтобы в каждой строке сумма оставшихся чисел не превосходила $\frac{n + 1}{4}$.
Решение:
Пусть в верхней строке стоят числа $a_1, a_2, \cdots, a_n$. Переставим столбцы так, что $a_1 \leq a_2 \leq \cdots \leq a_n$. Тогда в нижней строке стоят соответственно $b_1 = 1 - a_1, b_2 = 1 - a_2, \cdots, b_n = 1 - a_n$; ясно, что $b_1 \geq b_2 \cdots b_n$. Если $a_1 + a_2 + \cdots + a_n \leq \frac{n+1}{4}$, то вычеркнем все числа нижней строки. Иначе найдем минимальный номер $k$ такой, что $a_1 + a_2 + \cdots + a_k > \frac{n+1}{4}$, вычеркнем в верхней строке числа $a_k, a_{k+1}, \cdots, a_n$, а в нижней - $b_1, b_2,\cdots, b_{k-1}$. По выбору $к$ имеем $a_1 + \cdots + a_{k-1} \leq \frac{n+1}{4}$. Остается доказать, что $b_k + b_{к+1} + \cdots + b_n \leq \frac{n+1}{4}$.
Поскольку $a_k \geq \frac{a_1+ \cdots + a_k}{k} > \frac{n+1}{4k}$, имеем
$b_k + b_{k+1} + \cdots + b_n \leq (n+1 - k)b_k = (n+1 -k)(1-a_k) < (n+1-k)(1- \frac{n+1}{4k}) = \frac{5}{4}(n+1) - [\frac{(n+1)^2 + (2k)^2}{4k}] \leq \frac{5}{4}(n+1) - \frac{2(n+1)(2k)}{4k} = \frac{n+1}{4}$.
