Олимпиадная задача по индукции и комбинаторике: цемент на 2011 складах, 10-11 класс

   Пусть (при произвольной схеме дорог) изначально весь цемент расположен на одном складе S, а распределить его нужно по всем складам поровну. Тогда на каждый склад, кроме S, нужно в каком-нибудь рейсе цемент завезти, поэтому всего рейсов должно быть не меньше 2010.

   Докажем индукцией по n, что при n складах всегда удастся обойтись  n – 1  рейсом. База  (n = 1)  очевидна.

   Шаг индукции. Пусть  n > 1.  Так как с каждого склада можно добраться до любого другого, то существует маршрут, проходящий по всем складам (может быть, неоднократно). Рассмотрим такой маршрут и склад A, который впервые появился на этом маршруте позже всего. Тогда, если удалить склад A и все дороги, ведущие из него, то по-прежнему от любого склада до любого другого можно добраться.

   Можно считать, что A – склад с номером n. Если  y_n ≤ x_n,  то вывезем из A на любой соединённый с ним склад  x_n – y_n  кг цемента, а после этого забудем про него и про все дороги, из него ведущие. По предположению индукции, для оставшихся складов можно выполнить план за  n – 2  рейса. В итоге через  n – 1  рейс получится требуемое распределение цемента.

   Пусть  y_n > x_n.  Мы уже доказали, что из распределения, когда на i-м складе находится y_i кг, можно за  n – 1  рейс получить распределение, когда на i-м складе находится x_i кг. Проведя все эти перевозки в обратном порядке (и обратном направлении), мы осуществим требуемый план.

За 2010 рейсов.