Задача
COM-B1-M05-P021 Две непересекающиеся группы
#21
★★★★☆ Уровень 4 из 5
Докажите, что среди любых \(10\) натуральных чисел, не превосходящих \(99\), можно выбрать две непустые непересекающиеся группы с одинаковой суммой.
Сначала найдите две разные группы с одинаковой суммой, затем удалите общие элементы.
Непустых подмножеств \(1023\). Их суммы лежат от \(1\) до \(990\), возможных сумм не более \(990\). Значит есть два разных непустых подмножества с равной суммой. Удалим из них общие элементы. Оставшиеся части имеют равные суммы; они не обе пусты, иначе исходные подмножества совпадали бы. Получили две непустые непересекающиеся группы с равной суммой.
Сильная версия subset-sum Дирихле.