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

Проект МЦНМО
при участии
школы 57
Задача 97838
Темы:    [ Раскладки и разбиения ]
[ Подсчет двумя способами ]
Сложность: 5
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

  Для каждого натурального 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

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

журнал
Название "Квант"
год
Год 1984
выпуск
Номер 9
Задача
Номер М885
олимпиада
Название Турнир городов
Турнир
Дата 1983/1984
Номер 5
вариант
Вариант весенний тур, основной вариант, 9-10 класс
Задача
Номер 5

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

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