Задача 61513

Темы:    [ Раскладки и разбиения ] [ Двоичная система счисления ] [ Четность и нечетность ] [ Мощность множества. Взаимно-однозначные отображения ]

Сложность: 4- Классы: 8,9,10,11

Условие

Придумайте какое-либо взаимно-однозначное соответствие между разбиениями натурального числа на различные и на нечётные слагаемые.

Решение

Пусть есть разбиение числа n на различные слагаемые. Каждое чётное слагаемое вида 2^km, где m нечётно, разобьём дополнительно на 2^k слагаемых, равных m. Получим разбиение n на нечётные слагаемые. Исходное разбиение однозначно восстанавливается по полученному. Действительно, пусть в нём оказалось l слагаемых, равных m. Представим l в виде суммы  l = 2^k₁ + ... + 2^k_s  различных степеней двойки (как известно, это можно сделать единственным способом) и восстановим слагаемые  2^k₁m, ..., 2^k_sm  исходного разбиения.

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

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	11
Название	Последовательности и ряды
Тема	Последовательности
параграф
Номер	3
Название	Производящие функции
Тема	Производящие функции
задача
Номер	11.086