|
|
 |
Условие
На съезд собрались 5000 кинолюбителей, каждый видел хотя бы один фильм. Их делят на секции двух типов: либо обсуждение фильма, который все члены секции видели, либо каждый рассказывает о виденном фильме, который больше никто в секции не видел. Докажите, что всех можно разбить ровно на 100 секций. (Секции из одного человека разрешаются: он пишет отзыв о виденном фильме.)
Решение
Достаточно распределить участников съезда не более чем по 100 секциям: потом число секций можно поднять до 100, деля их на произвольные части.
Если есть фильм, который видели больше 100 человек, выделим их всех в отдельную секцию. Если теперь есть фильм, который видели больше 99 из оставшихся, выделим их в следующую секцию, и т.д. Если это удается делать, пока все люди не распределены, то 101 секция образоваться не могла
(101 + 100 + 99 + ... + 2 + 1 > 5000).
Пусть уже есть 100 – k секций и среди оставшихся участников каждый фильм видело не более k человек. Выделим k комнат для k новых секций. Берём любой фильм, распределяем видевших его по разным комнатам и поручаем им рассказывать об этом фильме. Так же поступаем с видевшими следующий фильм и продолжаем это, пока участники не кончатся.
Замечания
6 баллов
