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

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

Условие

Автор: Карасев Р.

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. Если  ynxn,  то вывезем из A на любой соединённый с ним склад  xnyn  кг цемента, а после этого забудем про него и про все дороги, из него ведущие. По предположению индукции, для оставшихся складов можно выполнить план за  n – 2  рейса. В итоге через  n – 1  рейс получится требуемое распределение цемента.
   Пусть  yn > xn.  Мы уже доказали, что из распределения, когда на i-м складе находится yi кг, можно за  n – 1  рейс получить распределение, когда на i-м складе находится xi кг. Проведя все эти перевозки в обратном порядке (и обратном направлении), мы осуществим требуемый план.


Ответ

За 2010 рейсов.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2010-2011
Этап
Вариант 4
класс
Класс 11
Задача
Номер 11.4

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

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