Задача 67312
|
|
 |
Условие
В клуб любителей гиперграфов в начале года записались $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 заседаний). Тогда каждый школьник познакомился с остальными десятью на самом первом заседании.
