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