Множество чисел назовём отличным, если его можно...

Задание:

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

а) Является ли множество {300; 301; 302;.. .399} отличным?

б) Является ли множество {3; 9; 2 7 ;... З¹⁰⁰} отличным?

в) Сколько отличных четырёхэлементных подмножеств у множества {1; 4; 5; 7; 8; 10; 17}.

Решение:

а) Разобьём множество {300; 301; 302; . . . 399} на 50 пар, сумма чисел в каждой из которых равна 699: {300; 399}, {301; 398}, . . . .

Множество {300; 301; 302; . . . 399} можно разбить на два подмножества, в каждом из которых по 25 таких пар. Значит, сумма в этих двух подмножествах одинакова и множество {300; 301; 302; . . . 399} является отличным.

б) Заметим, что 3¹⁰⁰ > (3¹⁰⁰ − 1) / 2 = 3⁹⁹ + 3⁹⁸ + . . . + 9 + 3 + 1. Поэтому сумма чисел в подмножестве множества {3; 9; 27; . . . 3¹⁰⁰}, содержащем 3¹⁰⁰ , всегда больше суммы остальных чисел, следовательно, множество {3; 9; 27; . . . 3¹⁰⁰} не является отличным.

в) Заметим, что четырёхэлементное множество является отличным в двух случаях: либо одно число является суммой трёх других, либо множество содержит две пары чисел с равными суммами.

Подмножества множества {1; 4; 5; 7; 8; 10; 17}, удовлетворяющие первому случаю, — это {1; 4; 5; 10}, {4; 5; 8; 17}.

Рассмотрим второй случай. Заметим, что сумма всех чисел отличного подмножества чётна. В исходном множестве три чётных (4, 8, 10) и четыре нечётных (1, 5, 7, 17) числа. Возможны случаи: чётное + чётное (Ч + Ч) = нечётное + нечётное (Н + Н), Н + Н = Н + Н, и Ч + Н = Ч + Н.

1) Ч + Ч = Н + Н. Переберём суммы чётных чисел.

4 + 8 = 5 + 7, {4; 5; 7; 8};

10 + 8 = 1 + 17, {1; 8; 10; 17};

4 + 10 = ? — Нет подходящих решений.

2) Н + Н = Н + Н.

17 + 1 > 5 + 7. — Нет подходящих решений.

3) Ч + Н = Ч + Н. Разность чётных чисел равна разности нечётных.

4 + 5 = 8 + 1, {1; 4; 5; 8};

4 + 7 = 10 + 1, {1; 4; 7; 10};

8 + 7 = 10 + 5, {5; 7; 8; 10}.

Всего получилось 7 отличных подмножеств.

Ответ: а) да; б) нет; в) 7.