Множество чисел назовем хорошим, если его можно разбить на два подмножества с одинаковой суммой чисел.
а) Является ли множество \(\left \{ 200; 201; 202; . . . ; 299\right \}\) хорошим?
б) Является ли множество \(\left \{ 2; 4; 8; . . . ; 2^{ 100}\right \}\) хорошим?
в) Сколько хороших четырёхэлементных подмножеств у множества \(\left \{ 1; 2; 4; 5; 7; 9; 11\right \}\)?
Решение.
а) Заметим, что числа 200, 201… 299 образуют арифметическую прогрессию.
Множество \(A = \left \{ 200, 201, . . . , 299\right \}\) можно разбить на 50 пар с равной суммой чисел в каждой паре: (200, 299), (201, 298), . . . , (249, 250). Числа из первых 25 пар пусть образуют множество \(A_1\), остальные числа — множество \(A_2.\) Тогда \(A = A_1 \cup A_2,\) причём суммы чисел в подмножествах \(A_1\) и \(A_2\) равны. Следовательно, A — хорошее множество.
б) Первый способ. Заметим, что все числа множества \(B = \left \{ 2, 4, 8, . . . , 2^{ 100}\right \},\) кроме 2, делятся на 4. Разобьём множество B на два каких-либо подмножества. Будем считать, что число 2 находится во втором подмножестве. Тогда сумма чисел первого подмножества делится на 4, а сумма чисел второго — нет, и эти суммы не могут быть равны. Значит, множество B не является хорошим.
Второй способ. Разобьём множество B на два каких-либо подмножества. Будем считать, что число \(2^{100}\) находится в первом подмножестве. Тогда сумма чисел первого подмножества не меньше, чем \(2^{100},\) а сумма чисел второго подмножества не больше, чем
\(2+4+ \, \dots \, +2^{ 99} = 2^{100} - 2\)
Значит, суммы чисел в обоих подмножествах не могут быть равны, и поэтому множество B не является хорошим.
в) Множество не может быть хорошим, если сумма его чисел нечётна. Поэтому для того чтобы множество было хорошим, необходимо, чтобы оно содержало чётное количество нечётных чисел. Тогда сумма его чисел четна.
Хорошее четырёхэлементное подмножество множества \(M = \left \{ 1, 2, 4, 5, 7, 9, 11\right \}\) может содержать ровно два или четыре нечётных числа.
Значит, нам надо выбрать два числа из пяти нечётных или 4 числа из пяти нечетных.
Если вы знакомы с комбинаторикой, вы знаете, что два числа из 5 нечетных можно выбрать \(C^2_5 = 10\) способами.
Можно сделать это и без применения формул комбинаторики, перебором вариантов. Выпишем все возможные варианты, то есть подмножества. Всего получится десять подмножеств:
\(A_1 = \left \{ 1, 2, 4, 5\right \}; \) \(A_6= \left \{ 2, 4, 5, 9\right \};\)
\(A_2 = \left \{ 1, 2, 4, 7\right \};\) \(A_7= \left \{ 2, 4, 5, 11\right \};\)
\(A_3 = \left \{ 1, 2, 4, 9\right \};\) \(A_8= \left \{ 2, 4, 7, 9\right \};\)
\(A_4 = \left \{ 1, 2, 4, 11\right \};\) \(A_9= \left \{ 2, 4, 7, 11\right \};\)
\(A_5 = \left \{ 2, 4, 5, 7\right \};\) \(A_{ 10} = \left \{ 2, 4, 9, 11\right \}.\)
Проверка показывает, что хорошими являются только шесть из них: \(A_1, A_2, A_5, A_7, A_8\) и \(A_{ 10}\).
Обратите внимание, что перебор вариантов – не хаотичный, а упорядоченный.
Четыре числа из пяти нечётных можно выбрать \(C^4_5 = 5\) способами. Или, если не знакомы с комбинаторикой, просто выписать возможные подмножества. Всего 5 подмножеств:
\(B_1 = \left \{ 1, 5, 7, 9\right \}; \)
\(B_2 = \left \{ 1, 5, 7, 11\right \}; \)
\(B_3 = \left \{ 1, 5, 9, 11\right \}; \)
\(B_4 = \left \{ 1, 7, 9, 11\right \}; \)
\(B_5 = \left \{ 5, 7, 9, 11\right \}. \)
Хорошими являются только два из них: \(B_2\) и \(B_5 . \)
Получили, что множество M имеет 8 хороших четырёхэлементных подмножеств.
Ответ: а) да; б) нет; в) 8.
