Олимпиадная задача: Раздача платных дорог 10 компаниям – комбинаторика и математический анализ, 10-11 класс

Решение 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 распределим произвольно.

Ответ задачи отсутствует