Закл 2022
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
В стране 998 городов. Некоторые пары городов соединены двусторонними авиарейсами. Согласно закону, между любой парой городов
должно быть не больше одного рейса. Другой закон требует, чтобы для любой группы городов было не больше 
рейсов,
соединяющих два города этой группы, где 
— количество городов в группе. В настоящий момент законы соблюдены. Докажите, что
министерство развития может ввести несколько новых рейсов так, чтобы законы по-прежнему соблюдались, а общее количество рейсов в
стране стало равным 5000.
Источники:
Назовём набор городов критическим, если есть 
рейсов, соединяющих два города этой группы, где 
— количество городов в
группе. Тогда 
ибо иначе между городами группы есть не более
рейсов. Если группа из всех 998 городов критическая, то в стране уже 
рейсов.
В дальнейшем мы всегда предполагаем, что законы в любой момент соблюдены. Обозначим через 
количество рейсов,
соединяющих два города группы 
Докажем, что если группа из всех городов не критическая, то министерство может добавить один рейс с соблюдением
законов. Повторяя такие операции, министерство добьётся требуемого. Заметим, что, если между городами 
и 
нет
рейса, то добавить его министерство не может лишь в случае, когда оба города 
и 
входят в какую-то критическую
группу.
_________________________________________________________________________________________________________________________________________________________________________________
Лемма. Пусть 
и 
— критические группы. Тогда группа 
также критическая.
Доказательство. Положим
Пусть
тогда 
По условию, имеем
Заметим, что все рейсы, посчитанные в 
и 
учитываются также и в 
более того, если какой-то рейс
учтён и в 
и в 
то оба его конца лежат в 
то есть количество дважды учтённых рейсов равно 
Поэтому
Учитывая, что законы соблюдены, получаем 
что и требовалось.
_________________________________________________________________________________________________________________________________________________________________________________
Вернёмся к решению. Если в настоящий момент нет ни одной критической группы, можно добавить рейс между любой парой городов,
между которыми его ещё нет (такая пара найдётся!). Иначе, применяя лемму, получаем, что объединение всех критических групп — тоже
критическая группа 
по предположению, в ней 
городов. Пусть 
— город вне 
тогда 
не входит ни в какую
критическую группу.
Пусть из 
идёт 
рейсов в города из 
Поскольку группа 
не критическая, имеем
откуда 
С другой стороны, 
поэтому в 
есть город 
не соединённый рейсом с 
и города 
и 
не входят в
одну критическую группу. Значит, министерство может ввести рейс между 
и 
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
