|
|
 |
Условие
В государстве n городов, и между каждыми двумя из них курсирует экспресс (в обе стороны). Для каждого экспресса цены билетов "туда" и "обратно" равны, а для разных экспрессов эти цены различны. Докажите, что путешественник может выбрать начальный город, выехать из него и проехать последовательно на n – 1 экспрессах, платя за проезд на каждом следующем меньше, чем за проезд на предыдущем. (Путешественник может попадать несколько раз в один и тот же город.)
Решение 1
Уберём все экспрессы, а затем начнём запускать их обратно по одному в порядке возрастания цены (первым запустим самый дешёвый, вторым – самый дешёвый из остальных, и т. д.). В каждый момент в каждом городе будем писать максимальное количество экспрессов, на которых можно последовательно проехать, начав из этого города, так, чтобы цены проезда монотонно убывали.
В начальный момент все числа в городах равны нулю. Пусть в некоторый момент мы вводим экспресс, соединяющий города A и B, в которых до этого были написаны числа a и b соответственно. После введения нового экспресса в A будет число, не меньшее b + 1 (ибо теперь из A можно проехать новым экспрессом в B, а затем по маршруту длины b, начинавшемуся из B). Аналогично, в B будет написано число, не меньшее a + 1. Поэтому сумма чисел в A и B увеличится хотя бы на 2, а числа в остальных городах не уменьшатся. Значит, и сумма всех чисел в городах увеличится хотя бы на 2.
Таким образом, когда все экспрессы будут введены, сумма чисел в городах станет не меньше, чем n(n – 1). Значит, хотя бы в одном городе будет число, не меньшее n – 1. Это и означает наличие требуемого маршрута из этого города.
Решение 2
Разделим каждый экспресс, курсирующий между A и B, на два – идущий из A в B и идущий из B в A. Получились n(n – 1) полуэкспрессов. Мы построим n выделенных маршрутов (по одному, начинающемуся в каждом городе) так, чтобы цена поездки на каждом монотонно убывала, и каждый полуэкспресс содержался бы хотя бы в одном выделенном маршруте. Тогда один из выделенных маршрутов будет содержать не менее
n – 1 полуэкспресса.
Выделенный маршрут, начинающийся в городе A, выглядит так. Пусть A0 = A. Рассмотрим все полуэкспрессы A0X, выходящие из A0, и выберем из них полуэкспресс A0A1 максимальной цены a1. Затем рассмотрим все полуэкспрессы A1Y, выходящие из A1, цена которых меньше a1; если такие есть, выберем из них полуэкспресс A1A2 максимальной цены a2, и т. д. Маршрут заканчивается полуэкспрессом Ak–1Ak, если из Ak не выходит полуэкспрессов с ценой, меньшей ak.
Осталось показать, что каждый полуэкспресс BC попадёт хотя бы в один из выделенных маршрутов. Положим B1 = B, B0 = C, и пусть b1 – цена BC. Рассмотрим все полуэкспрессы XB1, ведущие в B1, с ценой, большей b1. Если такие есть, то выберем из них полуэкспресс B2B1 наименьшей цены b2. Далее рассмотрим все полуэкспрессы YB2, ведущие в B2, с ценой, большей b2. Выберем из них полуэкспресс B3B2 наименьшей цены b3, и т. д. Этот процесс выбора закончится, когда при некотором k полуэкспресс BkBk–1 – это полуэкспресс максимальной цены, выходящий из Bk. Согласно нашему построению выделенный маршрут, выходящий из Bk, последовательно пройдёт через Bk–1, ..., B1, B0, то есть будет содержать экспресс BC.
Замечания
1. При любом чётном n можно построить пример, показывающий, что монотонного маршрута из n экспрессов может и не существовать.
2. Нетрудно понять, что каждый полуэкспресс попадёт ровно в один из выделенных маршрутов.
