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

Проект МЦНМО
при участии
школы 57
Задача 65467
Темы:    [ Принцип крайнего (прочее) ]
[ Полуинварианты ]
Сложность: 4+
Классы: 8,9
В корзину
Прислать комментарий

Условие

У Деда Мороза было n сортов конфет, по k штук каждого сорта. Он распределил все конфеты как попало по k подаркам, в каждый – по n конфет, и раздал их k детям. Дети решили восстановить справедливость. Два ребёнка готовы передать друг другу по конфете, если каждый получает конфету сорта, которого у него нет. Всегда ли можно организовать серию обменов так, что у каждого окажутся конфеты всех сортов?


Решение

Возьмём ребёнка A с наименьшим количеством сортов. Если у него n сортов, то всё в порядке. Если нет, то какого-то сорта у него больше одной конфеты. Значит, у какого-то ребёнка B нет этого сорта вовсе. Но тогда у B найдётся сорт, которого нет у A. Пусть A и B обменяются этими сортами. Тогда у A количество сортов увеличится, а у B – не уменьшится. В результате сумма количеств сортов у детей увеличится. Повторяя этот процесс, когда-нибудь доведём её до максимума, когда у каждого будет по n сортов.

Ответ

Всегда.

Замечания

10 баллов

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

олимпиада
Название Турнир городов
Турнир
Дата 2015/16
Номер 37
вариант
Вариант осенний тур, сложный вариант, 8-9 класс
задача
Номер 7

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

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