Комбинаторика на ММО: графы, турниры, логика, конструктивы
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
В клуб любителей гиперграфов в начале года записались 
попарно незнакомых школьников. За год клуб провёл 100
заседаний, причём каждое заседание посетил хотя бы один школьник. Два школьника знакомились, если было хотя бы
одно заседание, которое они оба посетили. В конце года оказалось, что количество знакомых у каждого школьника не
меньше, чем количество заседаний, которые он посетил. Найдите минимальное значение 
при котором такое могло
случиться.
Источники:
Подсказка 1
Какого школьника было бы удобно рассматривать для получения оценки?
Подсказка 2
Возьмите школьника, посетившего наибольшее число заседаний. Пусть оно равно k. С каким количеством людей он точно познакомился?
Подсказка 3
Поскольку каждое из заседаний посетил хотя бы кто-то, он познакомился с nk ≥ 100 людьми. А если он познакомился с хотя бы k другими участниками клуба, мы нашли уже хотя бы k + 1 школьника. Что нам это дает?
Подсказка 4
k + 1 ≥ 100/n + 1, а всего школьников у нас n.
Подсказка 5
Следовательно, n ≥ 100/n + 1, откуда n ≥ 11. Осталось придумать пример.
Подсказка 6
Предположите, что некоторое заседание посетили все школьники.
Подсказка 7
Остальные заседания можно разбить на 11 групп по 9, их посетят по одному школьнику.
Оценка. Рассмотрим самого активного школьника, посетившего наибольшее количество заседаний, пусть их было 
Так как все
заседания посетил хотя бы кто-то, то 
С другой стороны, по условию этот школьник познакомился с хотя бы 
другими
участниками клуба, значит, мы нашли уже хотя бы 
школьника, хотя их всего 
Таким образом, 
откуда
Пример. Возьмём первое заседание, которое посетят все школьники, а остальные разобьём на 11 групп по 9 заседаний, их посетят по
одному школьнику. Скажем, что школьник под номером 
посетил заседания из 
-ой группы вместе с самым первым. Таким образом,
каждый участник посетил 10 заседаний. Тогда каждый школьник познакомился с остальными десятью на самом первом
заседании.
Замечание. Немного модернизируя оценку, можно показать более общий результат: для 
заседаний наименьшее возможное число
школьников при данных условиях равно 
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
