ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 34899
Тема:    [ Разбиения на пары и группы; биекции ]
Сложность: 2+
Классы:
В корзину
Прислать комментарий

Условие

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

Подсказка

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

Решение

Пусть имеется разложение n=(a1+...+a1)+(a2+...+a2)+...+(ak+...+ak), где a1,a2,...,ak - различные нечетные числа, причем ai повторяется в разложении li раз. Рассмотрим разложение чисел li по различным степеням двойки (т.е. рассмотрим двоичную запись чисел li): li=2ti+2si+... . Тогда легко видеть, что число n разлагается в сумму n=(2t1a1+2s1a1+...)+...+(2tkak+2skak+...), причем все слагаемые в этой сумме различны. Наоборот, если имеется разложение числа n на различные натуральные слагаемые, то каждое слагаемое представим в виде 2pq, где p - целое, а q - нечетное, можно заменить это слагаемое на 2p слагаемых, равных q. Получим разложение n на нечетные слагаемые. Нетрудно видеть, что нами построено взаимно однозначное соответствие между разложениями первого и второго вида, следовательно количества разложений первого и второго типа равны.

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

web-сайт
задача

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .