Задача 19 про набор сумм целых чисел

Условие

Задумано несколько целых чисел. Набор этих чисел и все их возможные суммы (по 2, по 3 и т.д.) выписывают на доске в порядке неубывания. Например, если задуманы числа 2, 3, 5, то на доске будет выписан набор 2, 3, 5, 5, 7, 8, 10.
а) На доске выписан набор -5, -2, 1, 3, 4, 6, 9. Какие числа были задуманы?
б) Для некоторых различных задуманных чисел в наборе, выписанном на доске, число 0 встречается ровно 6 раз. Какое наименьшее количество чисел могло быть задумано?
в) Для некоторых задуманных чисел на доске выписан набор. Всегда ли по этому набору можно однозначно определить задуманные числа?

Решение

Подробное решение пункта (а) приведено здесь

Для решения задачи полезно понимать - сколько сумм содержит итоговый набор для разного количества исходных чисел. Подробные рассуждения приведены здесь. Результаты:

Приведем решение для пункта (б)
б) Для некоторых различных задуманных чисел в наборе, выписанном на доске, число 0 встречается ровно 6 раз. Какое наименьшее количество чисел могло быть задумано?

1) Покажем, что среди исходных чисел нет нуля.
Пусть даны некоторые исходные не нулевые числа, они образуют набор итоговых сумм, среди которых k нулей. Добавим к исходному набору число ноль и определим новое количество нулевых сумм.
- Нулевые суммы из прежнего набора войдут в новый набор сумм (это k нулевых сумм)
- При сложении числа ноль с нулевыми суммами из прежнего набора получим ноль, т.е. добавится еще k нулевых сумм
- Само число ноль также считаем нулевой суммой
Получаем, что в новом наборе будет k + k +1 = 2k + 1 нулевых сумм, а это нечетное число.
По условию набор сумм содержит 6 нулей, значит среди исходных чисел нет нуля.

2) Одно исходное число и два исходных числа образуют наборы с количеством сумм меньшим 6.
Три исходных числа образуют набор из 7 сумм, но сами исходные числа не равны нулю, значит такой набор не может содержать 6 нулей.

4) Ответим на вопрос: сколько одинаковых сумм в наборе могут давать 2, 3 и 4 исходных числа одного знака? Для определенности будем рассуждать для положительных чисел:

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

4) Среди исходных чисел нет числа ноль, значит 6 нулей – это нулевые суммы. Чтобы получить нулевую сумму, исходный набор должен включать положительные и отрицательные числа.

5) Покажем, что у 4 исходных чисел набор сумм не может содержать 6 нулевых сумм.

Если среди четырех исходных чисел три числа одного знака и одно число другого знака: три числа одного знака дают не более двух равных чисел в наборе сумм, значит добавление одного числа другого знака может дать не более двух нулей в наборе сумм

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

Таким образом, четыре различных не нулевых исходных числа дают набор, в котором не более трех нулей.

6) Покажем, что у 5 исходных чисел набор сумм не может содержать 6 нулевых сумм.

Если среди пяти исходных чисел четыре числа одного знака и одно число другого знака: четыре числа одного знака дают не более двух разных пар равных чисел в наборе сумм, значит добавление одного числа другого знака может дать не более двух нулей в наборе сумм

Если среди пяти исходных чисел три числа одного знака и два числа другого знака: три числа одного знака дают не более двух равных чисел в наборе сумм, значит совмещая наборы построенные на трех числах одного знака и двух числах другого знака можем получить не более четырех нулей, т.к. только одно число из второго набора может быть противоположным для двух чисел из первого набора, а остальные два числа из второго набора могут быть противоположными только для одного числа (у каждого свое) из первого набора

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

7) Мы показали, что 6 нулей в наборе сумм может быть, если исходных чисел больше пяти. Приведем пример шести исходных чисел, которые образуют набор, включающий 6 нулей.

Положительные числа 4, 10, 14 дают набор:
4, 10, 14, 14, 18, 24, 28.
Отрицательные числа -24, -10, -4 дают набор:
-24, -10, -4, -34, -28, -14, -38.
Каждому положительному числу (кроме 18) соответствует только одно отрицательное число, в сумме с которым получаем ноль.
Значит среди сумм итогового набора ровно 6 нулей.

Все попарные комбинации выписанных положительных (7 штук) и отрицательных чисел (7 штук) дают 49 сумм, добавляем выписанные положительные и отрицательные числа (7 + 7 = 14 штук) и получаем 63 суммы итогового набора для 6 исходных чисел.

Значит, приведенный пример удовлетворяет условию.

Приведем решение для пункта (в)
в) Для некоторых задуманных чисел на доске выписан набор. Всегда ли по этому набору можно однозначно определить задуманные числа?
Для наборов -4, -10, 14 и -14, 4, 10 будет выписан один набор сумм:
-14, -10, -4, 0, 4, 10, 14