МОШ 2024, 10 класс, задача 3
В клуб любителей гиперграфов в начале года записались попарно незнакомых школьников. За год клуб провёл заседаний, причём каждое заседание посетил хотя бы один школьник. Два школьника знакомились, если было хотя бы одно заседание, которое они оба посетили. В конце года оказалось, что количество знакомых у каждого школьника не меньше, чем количество заседаний, которые он посетил. Найдите минимальное значение , при котором такое могло случиться.
(Д. Метелев)
Ответ
Ответ: .
Решение. Оценка. Рассмотрим самого активного школьника, посетившего наибольшее количество заседаний, пусть их было . Так как все заседания посетил хотя бы кто-то, то . С другой стороны, по условию этот школьник познакомился с хотя бы другими участниками клуба, значит, мы нашли уже хотя бы школьника, хотя их всего . Таким образом, , откуда .
Пример. Возьмём первое заседание, которое посетят все школьники, а остальные разобьём на групп по заседаний, их посетят по одному школьнику. Скажем, что школьник под номером посетил заседания из -ой группы вместе с самым первым (таким образом, каждый участник посетил заседаний). Тогда каждый школьник познакомился с остальными десятью на самом первом заседании.
Замечание. Немного модернизируя оценку, можно показать более общий результат: для заседаний наименьшее возможное число школьников при данных условиях равно .