Задача к ЕГЭ на тему «из прошлых лет» №106

Множество чисел назовём хорошим, если его можно разбить на два подмножества с одинаковой суммой чисел.

а) Является ли множество ${100;101;102;...;199}$ хорошим?

б) Является ли множество ${2;4;8;...;2200}$ хорошим?

в) Сколько хороших четырёхэлементных подмножеств у множества ${3;4;5;6;8;10;12}?$

а) Данное множество состоит из 100 подряд идущих натуральных чисел, тогда его можно разбить на 50 пар с одинаковыми суммами:

{100;199}, {101;198}, ..., {149;150}

Так как количество таких пар 50, то можно составить первое подмножество из всех элементов любых 25 из этих пар, а второе подмножество составить из всех остальных чисел.

б) Данное множество не является хорошим, так как $2200$ больше суммы всех остальных его элементов. Это следует из формулы

n−1 n 1+ 2+ ...+2 = 2 − 1

Покажем по индукции, что эта формула верна.

1) При $n =1$ имеем: $1= 21− 1.$ Это верное равенство.

2) Пусть теперь формула верна для $n= m,$ покажем, что тогда она верна и для $n =m + 1:$

1 +2 +...+ 2(m+1)−1 = 1 +2 +...+ 2m−1+ 2m

По предположению индукции сумма всех слагаемых без последнего равна $2m− 1,$ тогда вся сумма равна

2m − 1+ 2m =2 ⋅2m− 1= 2m+1 − 1

Что и требовалось.

Тогда можем оценить сумму

199 199 2 +4 +8 +...+ 2 =− 1+ 1+ 2+ 4+ 8+ ...+ 2 =

= −1+ 2200− 1 =2200− 2< 2200

в) Для элементов хорошего четырёхэлементного подмножества должно выполняться равенство одного из двух видов:

a+ b+ c= d, a+ b= c+ d

Равенство $a+ b+ c= d$ может быть выполнено только в случае $3+ 4+ 5 =12,$ так как сумма любых трёх других элементов больше любого элемента данного множества.

Рассмотрим теперь случай равенства вида $a+ b= c+ d.$

В данном множестве всего два нечётных элемента. Для хорошего четырёхэлементного подмножества понятно, что они либо оба содержатся в нём, либо оба не содержатся в нём.

Рассмотрим подходящие четырёхэлементные подмножества, содержащие числа 3 и 5. Так как $3 +5 = 8,$ что меньше суммы любых двух других элементов исходного множества, то в требуемом равенстве вида $a +b =c +d$ они должны стоять по разные стороны от знака равенства:

a+ 3 =c +5 ⇒ a− c= 2

Тогда на роль пары чисел $(a;c)$ подходят пары

(12;10), (10;8), (8;6), (6;4)

Всего таких пар 4, следовательно, в случае равенства вида $a +b =c +d$ есть ровно 4 хороших подмножества из 4 элементов, содержащих числа 3 и 5.

Остаётся рассмотреть подходящие четырёхэлементные подмножества, не содержащие чисел 3 и 5. Они, таким образом, являются подмножествами множества

{4;6;8;10;12}

В этом множестве всего 5 элементов, то есть искомое подмножество должно содержать все его элементы, кроме одного. Кроме того, ясно, что так как в множестве ${4;6;8;10;12}$ все элементы чётные, то в равенстве вида $a+ b= c+ d$ слева и справа должны стоять чётные числа. Тогда сумма всех четырёх чисел должна делиться на 4.

Следовательно, нельзя удалять из множества ${4;6;8;10;12}$ числа 6 или 10. Остаётся убедиться, что при удалении из него чисел 4, 8 или 12 будут получаться хорошие подмножества. Это видно из равенств

8+ 10= 6+ 12, 6 +10 =4 + 12, 4+ 10= 6+ 8

Таким образом, есть ровно 3 хороших подмножества исходного множества, не содержащие чисел 3 и 5.

Итого у исходного множества есть ровно $1+ 4+ 3= 8$ хороших четырёхэлементных подмножеств.