Высшая проба 2026, 10 класс, задача 3
(16 баллов) В некоторой стране городов, один из которых — столица. Некоторые пары городов соединены двусторонним железнодорожным сообщением, причём известно, что из любого города можно проехать в любой другой, пользуясь железнодорожным транспортом, а также что между любой парой городов проходит не более одной железной дороги. На каждой дороге установлен тариф проезда: , , или монет, не зависящий от направления проезда вдоль неё (но, возможно, неодинаковый по всей стране).
В день концерта многие жители страны решили посетить столицу. Каждый ехал из своего города в столицу самым дешёвым маршрутом, состоящим из нескольких железнодорожных проездов, а если таковых было несколько — выбирал любой. Известно, что каждой железной дорогой воспользовался хотя бы один из посетителей концерта. Найдите наибольшее возможное количество железных дорог в этой стране.
Ответ. .
Решение. Оценка. Для удобства разделим цены на и будем считать, что они равны , , , монет (это не повлияет на сравнение стоимостей проезда). Рассмотрим граф, в котором вершинами будут города, а рёбрами — железные дороги. Назовём удалённостью города наименьшую сумму (в монетах), которую нужно заплатить, чтобы приехать в столицу из этого города (удалённость столицы положим равной нулю). Путь из города в столицу, имеющий наименьшую цену, назовём экономичным.
Лемма. Подпуть экономичного пути экономичен.
Доказательство леммы. Зафиксируем произвольный город . Если некоторый экономичный путь из любого другого города проходит через , то всегда есть экономичный путь из , получаемый удалением отрезка пути перед (он не обязан быть единственным, но он точно обязан быть экономичным, в противном случае мы бы объединили отрезок от до и экономичный путь из , то получили бы экономичный путь из , который дешевле , что противоречит экономичности ). Поэтому всякий экономичный путь любого города, проходящий через , содержит некоторый экономичный путь из .
Следствие. Пусть — ребро стоимости между городами и . Тогда .
Доказательство. По условию, было частью какого-то экономичного пути (из некоторого города ), а значит, оно содержало и экономичный путь из или из , пусть из . Тогда и подпуть этого экономичного пути из , начинающийся в , обязан быть экономичным, а значит, и из тоже, следовательно, нормы городов и различаются ровно на .
Теперь заметим, что норма соседних городов отличается ровно на нечётное число. Таким образом, все города делятся на города с чётной и нечётной удалённостью, а соединёнными ребром оказываются в точности города с разной чётностью удалённости — следовательно, граф дорог является двудольным, где долям соответствуют все города с равной чётностью удалённости. В двудольном графе на вершинах не может быть больше рёбер.
Пример. Покажем, что ровно дорог быть могло. Пусть стоимость проезда на каждой дороге одинакова. Тогда каждый посетитель концерта из доли с нечётной нормой едет напрямую в столицу по одной дороге, поэтому каждое ребро между столицей и каждым нечётным городом могло быть использовано, а каждый посетитель из чётной доли (в которой находится столица) может выбрать любой путь из двух рёбер, первое из которых соединяет его город с каким-нибудь городом из нечётной доли, а второе — от этого города до столицы. Так как все пути имеют равную ценность, каждое ребро между чётным городом, отличным от столицы, и каждым нечётным городом могло быть использовано
Доказана правильная оценка и приведён подходящий пример.
Полная оценка без примера.
Приведён пример наили доказана одна из лемм.