Задача
COM-B2-M04-P016 Максимальная сумма без повторения
Пусть \(A\) — множество различных положительных целых чисел, и никакие два непустых различных подмножества \(A\) не имеют одинаковой суммы. Докажите, что если \(A\) содержит \(k\) чисел, то сумма всех чисел из \(A\) не меньше \(2^k-1\).
Упорядочьте числа по возрастанию и докажите нижнюю оценку для каждого следующего числа через суммы предыдущих.
Пусть сумма всех чисел из \(A\) равна \(S\). У множества \(A\) есть \(2^k\) подмножеств, если считать и пустое. По условию суммы различных непустых подмножеств различны; сумма пустого подмножества равна \(0\) и не совпадает с ними, потому что все числа положительны.
Значит, получаются \(2^k\) различных целых сумм. Каждая из них лежит между \(0\) и \(S\), а в этом промежутке ровно \(S+1\) целых чисел. Поэтому \(S+1\ge 2^k\), откуда \(S\ge 2^k-1\).
Эту задачу можно дать сильным ученикам после обсуждения жадного минимального выбора; формулировка требует аккуратной работы с суммами подмножеств.