|
|
 |
Условие
2011 складов соединены дорогами так, что от каждого склада можно проехать к любому другому, возможно, проехав по нескольким дорогам. На складах находится по x1, ..., x2011 кг цемента соответственно. За один рейс можно провезти с произвольного склада на другой по соединяющей их дороге произвольное количество цемента. В итоге на складах по плану должно оказаться по y1, ..., y2011 кг цемента соответственно, причём
x1 + x2 + ... + x2011 = y1 + y2 + ... + y2011. За какое минимальное количество рейсов можно выполнить план при любых значениях чисел xi и yi и любой схеме дорог?
Решение
Пусть (при произвольной схеме дорог) изначально весь цемент расположен на одном складе S, а распределить его нужно по всем складам поровну. Тогда на каждый склад, кроме S, нужно в каком-нибудь рейсе цемент завезти, поэтому всего рейсов должно быть не меньше 2010.
Докажем индукцией по n, что при n складах всегда удастся обойтись n – 1 рейсом. База (n = 1) очевидна.
Шаг индукции. Пусть n > 1. Так как с каждого склада можно добраться до любого другого, то существует маршрут, проходящий по всем складам (может быть, неоднократно). Рассмотрим такой маршрут и склад A, который впервые появился на этом маршруте позже всего. Тогда, если удалить склад A и все дороги, ведущие из него, то по-прежнему от любого склада до любого другого можно добраться.
Можно считать, что A – склад с номером n. Если yn ≤ xn, то вывезем из A на любой соединённый с ним склад xn – yn кг цемента, а после этого забудем про него и про все дороги, из него ведущие.
По предположению индукции, для оставшихся складов можно выполнить план за n – 2 рейса. В итоге через n – 1 рейс получится требуемое распределение цемента.
Пусть yn > xn. Мы уже доказали, что из распределения, когда на i-м складе находится yi кг, можно за n – 1 рейс получить распределение, когда на i-м складе находится xi кг. Проведя все эти перевозки в обратном порядке (и обратном направлении), мы осуществим требуемый план.
Ответ
За 2010 рейсов.
