Докажите, что в любом множестве, состоящем из 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 трехзначных чисел.
Объяснение: