Версия для печати
Убрать все задачи
2011 складов соединены дорогами так, что от каждого склада можно проехать к любому другому, возможно, проехав по нескольким дорогам. На складах находится по x1, ..., x2011 кг цемента соответственно. За один рейс можно провезти с произвольного склада на другой по соединяющей их дороге произвольное количество цемента. В итоге на складах по плану должно оказаться по y1, ..., y2011 кг цемента соответственно, причём
x1 + x2 + ... + x2011 = y1 + y2 + ... + y2011. За какое минимальное количество рейсов можно выполнить план при любых значениях чисел xi и yi и любой схеме дорог?

Решение
Квадратный лист бумаги разрезали на шесть кусков в форме выпуклых
многоугольников; пять кусков затерялись, остался один кусок в форме
правильного восьмиугольника (см. рисунок). Можно ли по одному этому
восьмиугольнику восстановить исходный квадрат?

Решение