Комбинаторика на Питергоре

Выберем учеников из первого кружка, рассадим их в разные кабинеты. Выберем других человек из второго кружка и рассадим их, и так далее.

_________________________________________________________________________________________________________________________________________________________________________________

Замечание. Ученики школы посещают кружков. В каждый кружок ходит ровно детей. Всех учеников можно рассадить по кабинетам так, чтобы в каждом кабинете был хотя бы один представитель каждого кружка, даже если существенно больше Ниже мы докажем, что это можно сделать при

Рассмотрим комнат, где число определим позже. Посадим каждого школьника в одну из этих комнат, выбирая ее случайно (все комнаты равновероятны). Назовем комнату подозрительной, если в ней оказались представители не всех кружков. Предположим, что случилась УДАЧА: оказалось не более чем подозрительных комнат. Тогда имеется неподозрительных комнат, мы можем назвать их кабинетами, и искомая рассадка найдена. УДАЧА заведомо иногда случается, если математическое ожидание числа подозрительных комнат меньше Заметим, что равно количеству комнат умноженному на вероятность того, что конкретная комната подозрительна. Эта вероятность, в свою очередь, не превосходит Итак, если

то при таком требуемая рассадка существует. Уже при получается экспоненциальное по выражение, наилучшего результата — около — можно добиться при