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