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

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

Условие

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


Решение

Пусть Алёша записал k различных чисел  n1 < n2 < ... < nk.  Первое из записанных Серёжей чисел равно числу N1 коробок. Оно будет записано ровно n1 раз. После этого часть коробок опустеет, и следующее по величине число N2, записанное Серёжей, равно количеству коробок, где изначально было более n1 пирожных. Оно будет записано n2 раз. И т.д. Последнее по величине из записанных Серёжей чисел (Nk) равно количеству коробок, где изначально было nk пирожных.

Замечания

3 балла

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

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

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

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