Разделы 
Дополнительно
Задача по математике - 1635
2019-01-20 
Докажите, что в любом множестве, состоящем из 117 попарно раз личных трехзначных чисел, можно выбрать 4 попарно непересекающихся подмножества, суммы чисел в которых равны.
Решение:
Первое решение. Лемма. Из любых 61 различных трехзначных чисел можно выбрать две непересекающиеся пары чисел, суммы в которых равны.
Доказательство. Из 61 числа можно образовать $\frac{61 \cdot 60}{2} = 1830$ пар чисел, сумма чисел в каждой паре лежит между 200 и 2000, следовательно, у каких-то двух пар суммы совпадают. Пары, для которых совпадают суммы, очевидно, не могут пересекаться, ибо если $x + y = x + z$, то $y = z$ и пары совпадают. Лемма доказана.
Выберем пару пар чисел с равными суммами 15 раз (каждый раз будем исключать из рассматриваемого набора 4 взятых числа, перед последующим выбором чисел останется как раз 61 число). Если не все 15 сумм были различны, то мы нашли 4 искомых множества - это 4 пары чисел, у которых совпадают суммы.
Если все 15 сумм различны, то составим два множества пар $N_{1}$ и $N_{2}$ таким образом: из двух пар с равными суммами первую включим в $N_{1}$, вторую - в $N_{2}$. Рассмотрим первое множество пар. У него есть $2^{15}$ подмножеств. Сумма всех чисел во всех парах любого подмножества не превосходит 30 000 тысяч (чисел не больше 30, каждое меньше тысячи).
Но $2^{15} > 30 000$, следовательно, есть два подмножества, для которых суммы чисел, входящих во все их пары, совпадают. Выбросив из этих подмножеств их пересечение, получим непересекающиеся подмножества $M_{1}$ и $M_{2}$ с тем же условием.
Теперь в $N_{2}$ возьмем подмножества пар, соответствовавших парам из множеств $M_{1}$ и $M_{2} - M_{3}$ и $M_{4}$. Множества чисел, входящих в пары $M_{1}, M_{2}, M_{3}, M_{4}$ - искомые.
Комментарий. Из аналогичных соображений выбирая не только пары, но также тройки и четверки, можно показать, что четыре непересекающиеся подмножества с равными суммами можно выбрать среди любых 97 трехзначных чисел.
Второе решение. Покажем, что среди произвольных 106 чисел существуют даже четыре непересекающихся пары с равными суммами. Доказательство абсолютно аналогично вышеприведенной лемме. Из 106 чисел можно образовать $\frac{106 \cdot 105}{2} = 5460$ пар чисел, сумма чисел в каждой паре лежит между 200 и 2000. Если пар с любой суммой не более трех, то всего пар не более $1800 \cdot 3 = 5400$, что не так. Следовательно, у каких- то четырех пар суммы совпадают. Пары, для которых совпадают суммы, очевидно, не могут пересекаться, ибо если $x + y = x + z$, то $y = z$ и пары совпадают.
Докажите, что в любом множестве, состоящем из 117 попарно раз личных трехзначных чисел, можно выбрать 4 попарно непересекающихся подмножества, суммы чисел в которых равны.
Решение:
Первое решение. Лемма. Из любых 61 различных трехзначных чисел можно выбрать две непересекающиеся пары чисел, суммы в которых равны.
Доказательство. Из 61 числа можно образовать $\frac{61 \cdot 60}{2} = 1830$ пар чисел, сумма чисел в каждой паре лежит между 200 и 2000, следовательно, у каких-то двух пар суммы совпадают. Пары, для которых совпадают суммы, очевидно, не могут пересекаться, ибо если $x + y = x + z$, то $y = z$ и пары совпадают. Лемма доказана.
Выберем пару пар чисел с равными суммами 15 раз (каждый раз будем исключать из рассматриваемого набора 4 взятых числа, перед последующим выбором чисел останется как раз 61 число). Если не все 15 сумм были различны, то мы нашли 4 искомых множества - это 4 пары чисел, у которых совпадают суммы.
Если все 15 сумм различны, то составим два множества пар $N_{1}$ и $N_{2}$ таким образом: из двух пар с равными суммами первую включим в $N_{1}$, вторую - в $N_{2}$. Рассмотрим первое множество пар. У него есть $2^{15}$ подмножеств. Сумма всех чисел во всех парах любого подмножества не превосходит 30 000 тысяч (чисел не больше 30, каждое меньше тысячи).
Но $2^{15} > 30 000$, следовательно, есть два подмножества, для которых суммы чисел, входящих во все их пары, совпадают. Выбросив из этих подмножеств их пересечение, получим непересекающиеся подмножества $M_{1}$ и $M_{2}$ с тем же условием.
Теперь в $N_{2}$ возьмем подмножества пар, соответствовавших парам из множеств $M_{1}$ и $M_{2} - M_{3}$ и $M_{4}$. Множества чисел, входящих в пары $M_{1}, M_{2}, M_{3}, M_{4}$ - искомые.
Комментарий. Из аналогичных соображений выбирая не только пары, но также тройки и четверки, можно показать, что четыре непересекающиеся подмножества с равными суммами можно выбрать среди любых 97 трехзначных чисел.
Второе решение. Покажем, что среди произвольных 106 чисел существуют даже четыре непересекающихся пары с равными суммами. Доказательство абсолютно аналогично вышеприведенной лемме. Из 106 чисел можно образовать $\frac{106 \cdot 105}{2} = 5460$ пар чисел, сумма чисел в каждой паре лежит между 200 и 2000. Если пар с любой суммой не более трех, то всего пар не более $1800 \cdot 3 = 5400$, что не так. Следовательно, у каких- то четырех пар суммы совпадают. Пары, для которых совпадают суммы, очевидно, не могут пересекаться, ибо если $x + y = x + z$, то $y = z$ и пары совпадают.
