Разделы 
Дополнительно
Задача по математике - 3558
2019-06-12 
Даны $n$ различных положительных чисел $a_1, a_2, a_n$. Из них составляются всевозможные суммы с любым числом слагаемых (от 1 до $n$). Докажите, что среди этих сумм найдется по крайней мере $\frac{n(n + 1)}{2}$ попарно различных.
Решение:
Можно считать, что числа расположены в порядке возрастания: $a_1 < a_2 < \cdots < a_n$. Рассмотрим числа:
Очевидно, что здесь каждое число больше предыдущего; таким образом, все выписанные числа различны. Их количество
$n + (n - 1) + \cdots + 1 = \frac{n(n+1)}{2}$ соответствует требованиям задачи.
Заметим еще, что первые $n$ натуральных чисел дают пример $n$ различных чисел, из которых нельзя составить больше чем $\frac{n(n + 1)}{2}$ различных сумм (эти суммы - все натуральные числа от 1 до $1 + 2 + \cdots + n = \frac{n(n+ 1)}{2}$).
Даны $n$ различных положительных чисел $a_1, a_2, a_n$. Из них составляются всевозможные суммы с любым числом слагаемых (от 1 до $n$). Докажите, что среди этих сумм найдется по крайней мере $\frac{n(n + 1)}{2}$ попарно различных.
Решение:
Можно считать, что числа расположены в порядке возрастания: $a_1 < a_2 < \cdots < a_n$. Рассмотрим числа:
Очевидно, что здесь каждое число больше предыдущего; таким образом, все выписанные числа различны. Их количество
$n + (n - 1) + \cdots + 1 = \frac{n(n+1)}{2}$ соответствует требованиям задачи.
Заметим еще, что первые $n$ натуральных чисел дают пример $n$ различных чисел, из которых нельзя составить больше чем $\frac{n(n + 1)}{2}$ различных сумм (эти суммы - все натуральные числа от 1 до $1 + 2 + \cdots + n = \frac{n(n+ 1)}{2}$).
