Соответствия, сравнения, количества

Так как по условию нам дано множество, то элементы в нём не повторяются. Давайте сначала смотреть на двухэлементные подмножества, их всего штук. Понятно, что у них не могут совпадать суммы, и они пересекаются, так как иначе они просто совпадают. Если множеств, подходящих под условие нашлось штуки, то мы победили. Но возможных сумм двухэлементных множеств и если бы их было хотя бы то да — мы бы решили задачу. Значит, у нас максимум два множества с двумя элементами и одинаковой суммой.

Давайте теперь посмотрим на возможные подмножества из трёх элементов, их штук. Понятно, что множества с одинаковой суммой могут пересекаться максимум по одному элементу, потому что иначе аналогично предыдущему рассуждению они полностью совпадают. Если же все три множества пересекаются по одному элементу, то сумма у них не может быть одинаковая. Действительно, в таком случае мы уже нашли подходящие множества из двух элементов. Возможных же сумм может быть только поэтому точно найдётся троек с какой-то одинаковой суммой. Пусть это множества Давайте теперь рассмотрим граф на вершинах, обозначающих множества. Они будут соединяться ребром, если имеют общий элемент, и будем подписывать ребро этим элементом. Как мы поняли, кратных рёбер между ними нет, и максимум из одной вершины могут идти ребра с разным элементом. Таким образом, не умаляя общности пусть из вершины рёбра ведут в а из — в Таким образом, у нас остались вершины и не соединённые ребром между собой. Победа, задача решена.