|
|
 |
Условие
В стране две столицы и несколько городов, некоторые из них соединены дорогами. Среди дорог есть платные. Известно, что на любом пути из южной столицы в северную имеется не меньше 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 баллов.
