ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 64768
Темы:    [ Процессы и операции ]
[ Принцип крайнего (прочее) ]
[ Принцип Дирихле (прочее) ]
Сложность: 5-
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

В государстве 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 = BB0 = 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. Нетрудно понять, что каждый полуэкспресс попадёт ровно в один из выделенных маршрутов.

Источники и прецеденты использования

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2013-2014
этап
Вариант 5
класс
Класс 9
задача
Номер 9.8

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .