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

289

337

Посмотреть ответы 2

Ответы на вопрос:

222111ALEXA111222

Обществознание

4,7(95 оценок)

Лемма.

Из любых 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 трехзначных чисел.

Объяснение:

sxpidxoznitsxa

Обществознание

4,6(19 оценок)

Мне кажется верно только б

Реши свою проблему, спроси otvet5GPT

Быстро
Мгновенный ответ на твой вопрос
Точно
Бот обладает знаниями во всех сферах
Бесплатно
Задай вопрос и получи ответ бесплатно

Задай свой вопрос

Популярно: Обществознание

Есть вопросы?

Как otvet5GPT работает?

otvet5GPT использует большую языковую модель вместе с базой данных GPT для обеспечения высококачественных образовательных результатов. otvet5GPT действует как доступный академический ресурс вне класса.
Сколько это стоит?

Проект находиться на стадии тестирования и все услуги бесплатны.
Могу ли я использовать otvet5GPT в школе?

Конечно! Нейросеть может помочь вам делать конспекты лекций, придумывать идеи в классе и многое другое!
В чем отличия от ChatGPT?

otvet5GPT черпает академические источники из собственной базы данных и предназначен специально для студентов. otvet5GPT также адаптируется к вашему стилю письма, предоставляя ряд образовательных инструментов, предназначенных для улучшения обучения.