Задача 65467
|
|
 |
Условие
У Деда Мороза было n сортов конфет, по k штук каждого сорта. Он распределил все конфеты как попало по k подаркам, в каждый – по n конфет, и раздал их k детям. Дети решили восстановить справедливость. Два ребёнка готовы передать друг другу по конфете, если каждый получает конфету сорта, которого у него нет. Всегда ли можно организовать серию обменов так, что у каждого окажутся конфеты всех сортов?
Решение
Возьмём ребёнка A с наименьшим количеством сортов. Если у него n сортов, то всё в порядке. Если нет, то какого-то сорта у него больше одной конфеты. Значит, у какого-то ребёнка B нет этого сорта вовсе. Но тогда у B найдётся сорт, которого нет у A. Пусть A и B обменяются этими сортами. Тогда у A количество сортов увеличится, а у B – не уменьшится. В результате сумма количеств сортов у детей увеличится. Повторяя этот процесс, когда-нибудь доведём её до максимума, когда у каждого будет по n сортов.Ответ
Всегда.
Замечания
10 баллов
