Задача 111648

Темы:    [ Раскладки и разбиения ] [ Подсчет двумя способами ]

Сложность: 3+ Классы: 10,11

Условие

Автор: Буфетов А.И.

У Алёши есть пирожные, разложенные в несколько коробок. Алёша записал, сколько пирожных в каждой коробке. Серёжа взял по одному пирожному из каждой коробки и положил их на первый поднос. Затем он снова взял по одному пирожному из каждой непустой коробки и положил их на второй поднос – и так далее, пока все пирожные не оказались разложенными по подносам. После этого Серёжа записал, сколько пирожных на каждом подносе. Докажите, что количество различных чисел среди записанных Алёшей равно количеству различных чисел среди записанных Серёжей.

Решение

Пусть Алёша записал k различных чисел  n₁ < n₂ < ... < n_k.  Первое из записанных Серёжей чисел равно числу N₁ коробок. Оно будет записано ровно n₁ раз. После этого часть коробок опустеет, и следующее по величине число N₂, записанное Серёжей, равно количеству коробок, где изначально было более n₁ пирожных. Оно будет записано n₂ раз. И т.д. Последнее по величине из записанных Серёжей чисел (N_k) равно количеству коробок, где изначально было n_k пирожных.

Замечания

3 балла

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

олимпиада
Название	Турнир городов
Турнир
Дата	2008/2009
Номер	30
вариант
Вариант	осенний тур, базовый вариант, 10-11 класс
задача
Номер	1