|
|
 |
Условие
Для каждого натурального n обозначим через P(n) число разбиений n в сумму натуральных слагаемых (разбиения, отличающиеся лишь порядком слагаемых, считаются одинаковыми; например, P(4) = 5, потому что 4 = 4 = 1 + 3 = 2 + 2 = 1 + 1 + 2 = 1 + 1 + 1 + 1 – пять способов).
а) Количество различных чисел в данном разбиении назовем его разбросом (например, разбиение 4 = 1 + 1 + 2 имеет разброс 2, потому что в этом разбиении два различных числа). Докажите, что сумма Q(n) разбросов всех разбиений числа n равна 1 + P(1) + P(2) + ... + P(n–1).
б) Докажите, что
Решение
а) Из каждого разбиения числа m < n можно единственным образом получить разбиение числа n, добавив n – m. Так получаются все разбиения числа n, кроме разбиения n = n.
С другой стороны, каждое разбиение n получается таким способом столько раз, каков его разброс: можно выкинуть любое из неравных слагаемых. Это и доказывает формулу.
б) Пусть k – наибольший из всех разбросов разбиений числа n. Тогда n ≥ 1 + 2 + ... + k > k²/2, то есть Умножив на количество разбиений, получим
Замечания
баллы: 9 + 3
