Задача 67312

Темы:    [ Теория графов (прочее) ] [ Оценка + пример ]

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

Условие

Автор: Метелев Д.

В клуб любителей гиперграфов в начале года записались $n$ попарно незнакомых школьников. За год клуб провёл $100$ заседаний, причём каждое заседание посетил хотя бы один школьник. Два школьника знакомились, если было хотя бы одно заседание, которое они оба посетили. В конце года оказалось, что количество знакомых у каждого школьника не меньше, чем количество заседаний, которые он посетил. Найдите минимальное значение $n$, при котором такое могло случиться.

Решение

Оценка. Рассмотрим самого активного школьника, посетившего наибольшее количество заседаний, пусть их было $k$. Так как каждое заседание посетил хотя бы кто-то, то $nk \ge 100$. С другой стороны, по условию этот школьник познакомился с хотя бы $k$ другими участниками клуба, значит, мы нашли уже хотя бы $k+1 \ge \frac{100}{n}+1$ школьника, хотя их всего $n$. Таким образом, $n \ge \frac{100}{n}+1$, откуда $n \ge 11$.

Пример. Пусть первое заседание посетят все 11 школьников, а остальные заседания разобьём на 11 групп по 9 заседаний, их посетят по одному школьнику. Скажем, что школьник под номером $i$ посетил заседания из $i$-й группы, а также самое первое (таким образом, каждый участник посетил 10 заседаний). Тогда каждый школьник познакомился с остальными десятью на самом первом заседании.

Ответ

11.

Замечания

Можно доказать аналогичную оценку в более общей ситуации: для $N$ заседаний наименьшее возможное число школьников при данных условиях равно $\lceil\sqrt{N}\rceil + 1$.

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

олимпиада
Название	Московская математическая олимпиада
год
Номер	87
Год	2024
класс
Класс	10
задача
Номер	3