Разделы 
Дополнительно
Задача по математике - 3765
2019-06-16 
Дано множество положительных чисел $\{a_1, a_2, \cdots, a_n \}$. Для каждого его подмножества выпишем сумму входящих в него чисел (рассматриваются суммы из одного, двух, ..., $n$ слагаемых). Докажите, что все выписанные числа можно так разбить на $n$ групп, чтобы в каждой группе отношение наибольшего числа к наименьшему не превосходило 2.
Решение:
Занумеруем данные числа в порядке возрастания: $a_1 \leq a_2 \leq \cdots \leq a_n$.
Докажем, что каждая сумма $s$ некоторых из них лежит в одном из промежутков между $b_k/2$ и $b_k$, где $b_k = a_1 + a_2 + \cdots + a_k$ ($k = 1, 2, \cdots, n$). Достаточно доказать, что никакая сумма $s$ не может оказаться строго между $b_k$ и $b_{k+1}/2$. Предположив, что $s > b_k = a_1 + a_2 + \cdots + a_k$, и, стало быть, $s$ содержит некоторое $a_i \geq a_{k+1}$, а потому $s \geq a_{k+1}$, мы получили бы (сложив неравенства), что $2s > a_1 + a_2 + \cdots + a_{k+1} = b_{k+1}$, т. е. $s > b_{k+1}/2$.
Дано множество положительных чисел $\{a_1, a_2, \cdots, a_n \}$. Для каждого его подмножества выпишем сумму входящих в него чисел (рассматриваются суммы из одного, двух, ..., $n$ слагаемых). Докажите, что все выписанные числа можно так разбить на $n$ групп, чтобы в каждой группе отношение наибольшего числа к наименьшему не превосходило 2.
Решение:
Занумеруем данные числа в порядке возрастания: $a_1 \leq a_2 \leq \cdots \leq a_n$.
Докажем, что каждая сумма $s$ некоторых из них лежит в одном из промежутков между $b_k/2$ и $b_k$, где $b_k = a_1 + a_2 + \cdots + a_k$ ($k = 1, 2, \cdots, n$). Достаточно доказать, что никакая сумма $s$ не может оказаться строго между $b_k$ и $b_{k+1}/2$. Предположив, что $s > b_k = a_1 + a_2 + \cdots + a_k$, и, стало быть, $s$ содержит некоторое $a_i \geq a_{k+1}$, а потому $s \geq a_{k+1}$, мы получили бы (сложив неравенства), что $2s > a_1 + a_2 + \cdots + a_{k+1} = b_{k+1}$, т. е. $s > b_{k+1}/2$.
