Задумано несколько целых чисел. Набор этих чисел и все их возможные суммы (по 2, по 3 и т. д.) выписывают на доску в порядке неубывания. Например, если задуманы числа 2, 3, 5, то на доске будет выписан набор 2, 3, 5, 5, 7, 8, 10.
а) На доске выписан набор −11, −7, −5, −4, −1, 2, 6. Какие числа были задуманы?
б) Для некоторых различных задуманных чисел в наборе, выписанном на доске, число 0 встречается ровно 4 раза. Какое наименьшее количество чисел могло быть задумано?
в) Для некоторых задуманных чисел на доске выписан набор. Всегда ли по этому набору можно однозначно определить задуманные числа?
Посмотреть решение
Предварительное решение, не проверено экспертом.
Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.
Шаг 1. Для n задуманных чисел выписано ровно 2n−1 непустых сумм с учётом повторений. Так находим n по длине списка. Каждое задуманное число присутствует в этом списке как одноэлементная сумма; поэтому для восстановления достаточно всех n-элементных наборов из данного списка, с различностью, если она требуется.
n=3
Шаг 2. Для каждого набора считаем все непустые суммы по подмножествам и сравниваем их с данным списком с учётом кратностей. В таблице все подходящие наборы. Конечная область охватывает каждое возможное решение.
T=((−7;−4;6))
Шаг 3. Записываем найденные значения.
(−7;−4;6)
Шаг 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))
Шаг 3. Записываем найденные значения.
5
Шаг 1. Два разных набора могут иметь один и тот же полный список непустых сумм. Приведённые две тройки различных целых чисел дают одинаковый список с теми же кратностями. Следовательно, однозначность для всех исходных наборов неверна.
T=((−3;1;2);(−2;−1;3);(−3;−2;−1;0;1;2;3))
Шаг 2. Нет. Полная конечная область или доказанное необходимое условие исключает возможность.