ВсОШ 2022, 9 класс, задача 7
( баллов) В стране городов. Некоторые пары городов соединены двусторонними авиарейсами. Согласно закону, между любой парой городов должно быть не больше одного рейса. Другой закон требует, чтобы для любой группы городов было не больше рейсов, соединяющих два города этой группы, где — количество городов в группе. В настоящий момент законы соблюдены. Докажите, что министерство развития может ввести несколько новых рейсов так, чтобы законы по-прежнему соблюдались, а общее количество рейсов в стране стало равным . (И. Богданов)
Ответ
Решение. Назовём набор городов критическим, если есть ровно рейсов, соединяющих два города этой группы, где — количество городов в группе (тогда , ибо иначе между городами группы есть не более рейсов). Если группа из всех городов критическая, то в стране уже рейсов.
В дальнейшем мы всегда предполагаем, что законы в любой момент соблюдены. Обозначим через количество рейсов, соединяющих два города группы .
Докажем, что если группа из всех городов не критическая, то министерство может добавить один рейс с соблюдением законов. Повторяя такие операции, министерство добьётся требуемого. Заметим, что, если между городами и нет рейса, то добавить его министерство не может лишь в случае, когда оба города и входят в какую-то критическую группу.
Лемма. Пусть и — критические группы. Тогда группа также критическая.
Доказательство. Положим , . Пусть , , ; тогда . По условию, имеем , и . Заметим, что все рейсы, посчитанные в и , учитываются также и в ; более того, если какой-то рейс учтён и в , и в , то оба его конца лежат в , то есть количество дважды учтённых рейсов равно . Поэтому
Учитывая, что законы соблюдены, получаем , что и требовалось.
Вернёмся к решению. Если в настоящий момент нет ни одной критической группы, можно добавить рейс между любой парой городов, между которыми его ещё нет (такая пара найдётся!). Иначе, применяя лемму, получаем, что объединение всех критических групп — тоже критическая группа ; по предположению, в ней городов. Пусть — город вне ; тогда не входит ни в какую критическую группу.
Пусть из идёт рейсов в города из . Поскольку группа не критическая, имеем
откуда . С другой стороны, , поэтому в есть город , не соединённый рейсом с , и города и не входят в одну критическую группу. Значит, министерство может ввести рейс между и .