Задача 34899

Тема:    [ Разбиения на пары и группы; биекции ]

Сложность: 2+ Классы:

Условие

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

Подсказка

Найдите соответствие между разложениями первого и второго видов.

Решение

Пусть имеется разложение n=(a₁+...+a₁)+(a₂+...+a₂)+...+(a_k+...+a_k), где a₁,a₂,...,a_k - различные нечетные числа, причем a_i повторяется в разложении l_i раз. Рассмотрим разложение чисел l_i по различным степеням двойки (т.е. рассмотрим двоичную запись чисел l_i): l_i=2^ti+2^si+... . Тогда легко видеть, что число n разлагается в сумму n=(2^t1a₁+2^s1a₁+...)+...+(2^tka_k+2^ska_k+...), причем все слагаемые в этой сумме различны. Наоборот, если имеется разложение числа n на различные натуральные слагаемые, то каждое слагаемое представим в виде 2^pq, где p - целое, а q - нечетное, можно заменить это слагаемое на 2^p слагаемых, равных q. Получим разложение n на нечетные слагаемые. Нетрудно видеть, что нами построено взаимно однозначное соответствие между разложениями первого и второго вида, следовательно количества разложений первого и второго типа равны.

Источники и прецеденты использования

web-сайт

задача