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

Проект МЦНМО
при участии
школы 57
Задача 116247
Темы:    [ Комбинаторика (прочее) ]
[ Принцип крайнего (прочее) ]
[ Соображения непрерывности ]
Сложность: 4-
Классы: 10,11
В корзину
Прислать комментарий

Условие

В стране две столицы и несколько городов, некоторые из них соединены дорогами. Среди дорог есть платные. Известно, что на любом пути из южной столицы в северную имеется не меньше 10 платных дорог. Докажите, что все платные дороги можно раздать 10 компаниям так, чтобы на любом пути из южной столицы в северную имелись дороги каждой из компаний.


Решение 1

  Отметим на каждом пути из южной столицы Ю в северную С первую платную дорогу числом 1. Докажем, что на каждом пути p осталось не менее 9 неотмеченных платных дорог.
  Выберем на p ближайшую к С отмеченную дорогу d. Поскольку она отмечена, она была первой платной на некотором пути q. Пройдём от Ю до d по (бесплатным дорогам) пути q, а далее через d вдоль p до C. По условию на таком пути не менее 10 платных дорог, и только дорога d отмечена. Значит, на участке пути от d до C есть не менее 9 неотмеченных платных дорог.
  Объявим временно отмеченные дороги бесплатными и отметим на каждом пути первую платную дорогу числом 2. Теперь на каждом пути останется не менее 8 платных дорог. Повторяя рассуждение, расставим отметки 3, ..., 10 на каждом пути.
  Теперь раздадим дороги компаниям в соответствии с их "номерами". Оставшиеся платные дороги раздадим произвольно.


Решение 2

  Пусть проезд по каждой платной дороге стоит 1 тугрик. Назовём весом дороги наименьшую сумму, которую надо заплатить, чтобы, выехав из Ю, добраться до этой дороги и проехать по ней (если до дороги вообще нельзя добраться из Ю, присвоим ей вес 100). По условию вес каждой дороги, входящей в С, не меньше 10.
  Заметим, что первая платная дорога на каждом пути из Ю в С имеет вес 1. При переходе к следующей дороге вес может увеличиться не более, чем на 1. Поэтому на каждом таком пути есть дороги любого веса от 1 до 10, причём первая дорога веса k на нем – платная.
  Отдадим k-й компании все дороги веса k, а дороги веса больше 10 распределим произвольно.

Замечания

1. Неявно предполагалось, что дороги односторонние. Разобраться с двусторонними дорогами не намного сложнее.

2. 5 баллов.

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

олимпиада
Название Турнир городов
Турнир
Дата 2009/2010
Номер 31
вариант
Вариант осенний тур, базовый вариант, 10-11 класс
Задача
Номер 5

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

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