Высшая проба 2024, 9 и 10 классы
( баллов) Многие учащиеся математического кружка остаются в нём преподавать после выпуска. Будем говорить, что Ваня является последователем Саши, если Ваня учился у Саши или если Ваня учился у ученика Саши, ученика ученика Саши и так далее. Преподаватель кружка называется народным, если у него есть последователи, и не менее половины из них — победители международной олимпиады IMO. Известно, что всего в кружке училось победителей IMO. Какое наибольшее количество народных преподавателей может быть в этом кружке, если у каждого человека не более одного учителя и никто не является собственным последователем?
Ответ
Ответ: .
Построим ориентированный граф, вершинами которого будут учащиеся и преподаватели кружка, а ребро проводится от учителя к его ученику. Таким образом, наш граф представляет собой набор непересекающихся деревьев.
Пример: Возьмём путь на вершине, ориентируем рёбра сверху вниз и в нижние вершин поставим победителей IMO. Тогда все вершины кроме самой нижней будут народными учителями.
Оценка: Рассмотрим все вершины, которые соответствуют народным учителям, никакой из предков которых не является народным учителем. Пусть в поддереве (не считая саму вершину) некоторой такой вершины победителей IMO. Поскольку выбранной вершине соответствует народный учитель, среди его последователей не более человек, не являющихся победителями IMO. Значит, всего в поддереве (считая корень) не более вершины. Из них народным учителям могут соответствовать не более вершин, так как найдётся хотя бы один человек, который никого не учил. Таким образом, число народных учителей в поддереве не может превышать число победителей IMO более чем в раза.
Поскольку поддеревья, соответствующие выбранным нами народным учителям, не пересекаются, просуммировав по ним число народных учителей, получим, что оно не превышает удвоенное число победителей, то есть .