Докажите, что в любом множестве, состоящем из 117 попарно различных трехзначных чисел, можно выбрать 4 попарно непересекающихся подмножества, суммы чисел в которых равны.

Лемма.

Из любых 61 различных трехзначных чисел можно выбрать две непересекающиеся пары чисел, суммы в которых равны.

Доказательство:

Из 61 числа можно образовать  пар чисел, сумма чисел в каждой паре лежит между 200 и 2000, следовательно, у каких-то двух пар суммы совпадают.

Пары, для которых совпадают суммы, очевидно, не могут пересекаться, ибо если x + y = x + z, то y = z и пары совпадают.

Лемма доказана.

Выберем пару пар чисел с равными суммами 15 раз (каждый раз будем исключать из рассматриваемого набора 4 взятых числа, перед последующим выбором чисел останется как раз 61 число).

Если не все 15 сумм были различны, то мы нашли 4 искомых множества — это 4 пары чисел, у которых совпадают суммы.

Если все 15 сумм различны, то составим два множества пар N1 и N2 таким образом: из двух пар с равными суммами первую включим в N1, вторую — в N2. Рассмотрим первое множество пар. У него есть 215 подмножеств.

Сумма всех чисел во всех парах любого подмножества не превосходит 30,000 тысяч (чисел не больше 30, каждое меньше тысячи).

Но 215 > 30\,000, следовательно, есть два подмножества, для которых суммы чисел, входящих во все их пары совпадают.

Выбросив из этих подмножеств их пересечение, получим непересекающиеся подмножества M1 и M2 с тем же условием.

Теперь в N2 возьмем подмножества пар, соответствовавших парам из множеств M1 и M2 — M3 и M4.

Множества чисел, входящих в пары M1, M2, M3, M4 — искомые.

Комментарий: Из аналогичных соображений выбирая не только пары, но также тройки и четверки, можно показать, что четыре непересекающиеся подмножества с равными суммами можно выбрать среди любых 97 трехзначных чисел.

Объяснение: