Top.Mail.Ru

Часто ищут

Разделы

Бесплатно

Тема . Графы и турниры

Деревья и остовные деревья

Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела графы и турниры
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#134202

Многие учащиеся математического кружка остаются в нём преподавать после выпуска. Будем говорить, что Ваня является последователем Саши, если Ваня учился у Саши или если Ваня учился у ученика Саши, ученика ученика Саши и так далее. Преподаватель кружка называется народным, если у него есть последователи, и не менее половины из них — победители международной олимпиады IMO. Известно, что всего в кружке училось 100 победителей IMO. Какое наибольшее количество народных преподавателей может быть в этом кружке, если у каждого человека не более одного учителя и никто не является собственным последователем?

Источники: Высшая проба - 2024, 10.4 (см. olymp.hse.ru)

Подсказки к задаче

Подсказка 1

У нас есть люди, причём некоторые из них связаны каким-то отношением... Всё это очень похоже на граф! Рассмотрим ориентированный граф, где вершины — это ученики и преподаватели кружка, а ребра ведут от учителя к его ученику. Каким будет этот граф?

Подсказка 2

Верно, это будет набор непересекающихся деревьев! Рассмотрим какого-нибудь народного учителя, не являющегося последователем другого народного учителя. Если среди его последователей k победителей IMO, то сколько среди них может быть народных учителей?

Подсказка 3

Общее число последователей не может быть больше 2k+1, значит, учителей среди них не больше 2k. Получается, в одном таком поддереве количество народных учителей не более, чем удвоенное количество победителей IMO. А верна ли эта оценка для всего графа?

Сообщить об ошибке
Подсказки
Ответ и решение
Сообщить об ошибке

Специальные программы

Все специальные программы

Программа
лояльности вер. 2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к твоему аккаунту.

Бесплатное онлайн-обучение

Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас важно быть полезными учителям по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!