Задача
Задумано несколько целых чисел. Набор этих чисел и все их возможные суммы (по 2, по 3 и т.д.) выписывают на доске в порядке неубывания. Например, если задуманы числа 2, 3, 5, то на доске будет выписан набор 2, 3, 5, 5, 7, 8, 10.
Примеры построения наборов сумм рассмотрены в здесь.
Ответим на вопрос: сколько чисел будет в итоговом наборе?
1 способ
Ясно, что одно исходное число дает набор из этого же одного числа.
Посчитаем, сколько сумм будет в наборе, образованном 2 исходными числами.
Затем добавим одно исходное число и посмотрим, как увеличится количество чисел в новом наборе.
Пусть дано 2 исходных числа (a, b), они образуют набор из трех чисел:
a, b, a + b.
Добавим одно исходное число (с).
Новый набор сумм содержит:
- три суммы из прежнего набора: a, b, a + b
- три суммы прежнего набора и нового числа:
a + c, b + c, a + b + c
- одно новое исходное число: с
Таким образом, количество сумм в новом наборе:
3 + 3 +1 = 7.
Пусть дано 3 исходных числа (a, b, c), они образуют набор из трех чисел:
a, b, с, a + b, a + c, b+ c, a + b + c
Добавим одно исходное число (d).
Новый набор сумм содержит:
- прежний набор: 7 чисел
- суммы прежнего набора и нового числа: 7 чисел
- новое исходное число: 1 число
Таким образом, количество сумм в новом наборе:
7 + 7 +1 = 15.
В общем виде:
Пусть дано n исходных чисел, они образуют набор из a(n) чисел.
Добавим одно исходное число.
Новый набор сумм содержит:
- прежний набор: a(n) чисел
- суммы прежнего набора и нового числа: a(n) чисел
- новое исходное число: 1 число
Таким образом, количество сумм в новом наборе:
a(n) + a(n) +1 = 2a(n) + 1.
Получили рекуррентную формулу.
Последовательность количества чисел в наборах сумм имеет вид:
1, 2*1 + 1 = 3, 2*3 + 1 = 7, 2*7 + 1 = 15, 2*15 + 1 = 31, 2*31 + 1 = 63, …
то есть
1, 3, 7, 15, 31, 63, ...
Примечание
Продолжи последовательность чисел
1, 3, 7, 15, 31, 63, …
Заметим, что разности между соседними числами – последовательные степени двойки: 2, 4, 8, 16, 32, …
2 способ
Проведем расчеты другим способом.
Количество сумм с фиксированным числом слагаемых можно посчитать как число сочетаний:
Например, дано четыре исходных числа, тогда
Итого: 4 + 6 + 4 + 1 = 15.
Аналогично для 5 исходных чисел:
Значит для n исходных чисел:
Заметим, что суммируются биномиальные коэффициенты:
При а = 1, b = 1 и без первого слагаемого получаем:
Значит для n исходных чисел количество чисел в итоговом наборе сумм равно