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

Проект МЦНМО
при участии
школы 57
Задача 116419
Темы:    [ Разбиения на пары и группы; биекции ]
[ Процессы и операции ]
[ Арифметическая прогрессия ]
Сложность: 4
Классы: 10,11
В корзину
Прислать комментарий

Условие

На съезд собрались 5000 кинолюбителей, каждый видел хотя бы один фильм. Их делят на секции двух типов: либо обсуждение фильма, который все члены секции видели, либо каждый рассказывает о виденном фильме, который больше никто в секции не видел. Докажите, что всех можно разбить ровно на 100 секций. (Секции из одного человека разрешаются: он пишет отзыв о виденном фильме.)


Решение

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

Замечания

6 баллов

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

олимпиада
Название Турнир городов
Турнир
Дата 2009/2010
Номер 31
вариант
Вариант весенний тур, основной вариант, 10-11 класс
Задача
Номер 4

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

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