Все суммы целых чисел

Последовательность применённых правил и переходов в пунктах задачи.

Учебный авторский материал. Порядок изучения не означает новую экспертную проверку решения или проверку источников.

Что разобрать сначала

Переходите по порядку или откройте то правило, которое вызвало затруднение. В конкретном решении используются только нужные для его условия ветви.

  1. Количество задуманных целых чисел
  2. Проверка полного списка сумм

    Сначала: Количество задуманных целых чисел

  3. Ответ

    Сначала: Проверка полного списка сумм

  4. Меньшие количества чисел невозможны

    Сначала: Ответ

  5. Достижение нужной кратности нуля

    Сначала: Меньшие количества чисел невозможны

  6. Ответ

    Сначала: Достижение нужной кратности нуля

  7. Неоднозначность восстановления

    Сначала: Ответ

  8. Ответ: нет

    Сначала: Неоднозначность восстановления

Разобранный пример

Задумано несколько целых чисел. Набор этих чисел и все их возможные суммы (по 2, по 3 и т. д.) выписывают на доску в порядке неубывания. Например, если задуманы числа 2, 3, 5, то на доске будет выписан набор 2, 3, 5, 5, 7, 8, 10.

а) На доске выписан набор −11-11, −7-7, −5-5, −4-4, −1-1, 2, 6. Какие числа были задуманы?

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

в) Для некоторых задуманных чисел на доске выписан набор. Всегда ли по этому набору можно однозначно определить задуманные числа?

Посмотреть решение

Предварительное решение, не проверено экспертом.

Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.

Шаг 1. Для nn задуманных чисел выписано ровно 2n−12^{n}-1 непустых сумм с учётом повторений. Так находим nn по длине списка. Каждое задуманное число присутствует в этом списке как одноэлементная сумма; поэтому для восстановления достаточно всех n-элементных наборов из данного списка, с различностью, если она требуется.
n=3n=3
Шаг 2. Для каждого набора считаем все непустые суммы по подмножествам и сравниваем их с данным списком с учётом кратностей. В таблице все подходящие наборы. Конечная область охватывает каждое возможное решение.
T=((−7;−4;6))\mathcal T=\left(\left(-7;-4;6\right)\right)
Шаг 3. Записываем найденные значения.
(−7;−4;6)\left(-7;-4;6\right)
Шаг 1. Для одного или двух различных целых чисел нулевая непустая сумма встречается не более одного раза. Для трёх различных чисел без нуля она встречается не более одного раза; с нулём возможны ровно 1 или 3 вхождения, но не 2. Для четырёх различных чисел без нуля не более двух противоположных пар; если обе пары есть, к ним добавляется только сумма всех четырёх. Нулевая тройка исключает другую нулевую тройку и не может сосуществовать с двумя противоположными парами. С одним нулём число нулевых сумм равно удвоенному количеству нулевых сумм оставшейся тройки плюс 1, то есть не больше 3. Поэтому 2 вхождения требуют не меньше четырёх чисел, а 4 или 7 вхождений - не меньше пяти.
Шаг 2. Приводим различные целые числа и перечисляем все их нулевые непустые суммы по индексам выбранных элементов. Их количество в точности равно заданному, поэтому нижняя граница числа задуманных чисел достигается.
T=((−6;−5;−1;1;5);(3;4);(2;5);(1;4;5);(2;3;4;5))\mathcal T=\left(\left(-6;-5;-1;1;5\right);\left(3;4\right);\left(2;5\right);\left(1;4;5\right);\left(2;3;4;5\right)\right)
Шаг 3. Записываем найденные значения.
55
Шаг 1. Два разных набора могут иметь один и тот же полный список непустых сумм. Приведённые две тройки различных целых чисел дают одинаковый список с теми же кратностями. Следовательно, однозначность для всех исходных наборов неверна.
T=((−3;1;2);(−2;−1;3);(−3;−2;−1;0;1;2;3))\mathcal T=\left(\left(-3;1;2\right);\left(-2;-1;3\right);\left(-3;-2;-1;0;1;2;3\right)\right)
Шаг 2. Нет. Полная конечная область или доказанное необходимое условие исключает возможность.

Открыть задачу целиком

Попробовать самостоятельно