Задача 66292

Темы:    [ Принцип Дирихле (прочее) ] [ Примеры и контрпримеры. Конструкции ]

Сложность: 3+ Классы: 8,9

Условие

В театральной труппе 60 актеров. Каждые два хотя бы раз играли в одном и том же спектакле. В каждом спектакле занято не более 30 актеров.
Какое наименьшее количество спектаклей мог поставить театр?

Решение

  Пример. Разобьём труппу на четыре группы по 15 человек и проведём 6 спектаклей, в каждом из которых задействованы какие-то две группы. Количество способов выбрать две группы из четырёх равно  4·3 : 2 = 6. 
  Оценка. В сумме актеры сыграли не более чем  30·5 = 150  ролей, значит, если спектаклей пять, то найдётся актер, сыгравший не более двух ролей. Тогда он сыграл в одном спектакле не более чем с  29·2 = 58  коллегами из остальных 59. Следовательно, для выполнения условия пяти спектаклей недостаточно.

Ответ

6 спектаклей.

Замечания

8 баллов

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

олимпиада
Название	Московская математическая регата
год
Год	2017/18
класс
Класс	9
задача
Номер	9.3.3