Как вы понимаете сделай первый шаг и ты поймёшь что не все так страшно. согласны ли вы? почему? пример. : )
Ответы на вопрос:
Лемма.
Из любых 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 трехзначных чисел.
Объяснение:
Популярно: Обществознание
-
Екатерина381730.06.2020 16:29
-
bititi223.02.2023 23:42
-
Maksimir90924.02.2023 17:48
-
whitesnaff22.10.2022 08:22
-
luda1234911.06.2023 09:08
-
khmelyuko27.09.2022 07:08
-
mazasa12809.03.2021 03:27
-
bigman403.04.2020 04:38
-
Sasho232505.02.2021 06:22
-
kapitan200102.06.2023 20:19