Всесиб 2025, отборочный этап, 8 класс, задача 5
( баллов) В НГУ учится студент. Некоторые из них посещают спецкурсы. Оказалось, что любые два спецкурса, если их посещают хотя бы два общих студента, имеют различное число участников. Докажите, что общее число спецкурсов в НГУ не превосходит миллиона, если на каждый спецкурс ходит по крайней мере человека.
Ответ
Решение. Рассмотрим сразу общий случай. Пусть студентов у нас всего . Докажем, что спецкурсов тогда не более .
Рассмотрим все спецкурсы, на которые ходят фиксированное количество человек. Пар студентов на одном таком спецкурсе занимается ровно , а каждая фиксированная пара из всех пар студентов НГУ принадлежит максимум одному рассматриваемому спецкурсу, ведь иначе по условию эти спецкурсы должны иметь разное число участников. Следовательно, всего спецкурсов на студентов может быть не более .
Просуммируем эту оценку по всем . Получим, что общее число спецкурсов не превосходит
Теперь заметим, что , то есть оценка переписывается в виде
что и требовалось доказать.