11.4. 2011 Warehouses are connected by roads in such a way that from any warehouse you can drive to any other, possibly by driving along several roads. On the warehouses, there are $x_{1}, \ldots, x_{2011}$ kg of cement respectively. In one trip, you can transport an arbitrary amount of cement from any warehouse to another warehouse along the road connecting them. In the end, according to the plan, there should be $y_{1}, \ldots, y_{2011}$ kg of cement on the warehouses respectively, with

$$
x_{1}+x_{2}+\ldots+x_{2011}=y_{1}+y_{2}+\ldots+y_{2011}
$$

What is the minimum number of trips required to fulfill the plan for any values of the numbers $x_{i}$ and $y_{i}$ and any road network?

(P. Karasev)
Answer. In 2010 trips.

Solution. First, we show that the plan cannot always be completed in 2009 trips. Suppose (with any road scheme) that initially all the cement is located at one warehouse $S$, and it needs to be evenly distributed to all warehouses. Then, cement must be delivered to each warehouse, except $S$, in some trip; it is clear that these 2010 trips are distinct, so the total number of trips must be at least 2010.

We need to show that the plan can always be completed in 2010 trips. We will prove by induction on $n$ that with $n$ warehouses, it is always possible to manage with $n-1$ trips. The base case for $n=1$ is obvious.

Let $n>1$. Since from any warehouse you can reach any other, there exists a route that passes through all warehouses (possibly more than once). Consider any such route and the warehouse $A$ that appears on this route the latest for the first time. Then, if we remove warehouse $A$ and all roads leading from it, it is still possible to reach any warehouse from any other (using the previous roads of the route).

We can assume that $A$ is the warehouse with number $n$. If $y_{n} \leqslant x_{n}$, then we will transport $x_{n}-y_{n}$ kg of cement from $A$ to any connected warehouse, and then forget about it and all roads leading from it. By the induction hypothesis, for the remaining warehouses, the plan can be completed in $(n-1)-1$ trips. In total, through $(n-2)+1$ trips, the required distribution of cement will be achieved.

If $y_{n}>x_{n}$, then we have already shown that from the distribution where the $i$-th warehouse has $y_{i}$ kg, it is possible to achieve the distribution where the $i$-th warehouse has $x_{i}$ kg in $n-1$ trips. By performing all these transports in reverse order (and in the opposite direction), we will implement the required plan.

Comment. Only the answer - 0 points.

Only an example is provided, showing that the plan cannot always be completed in 2009 trips - 2 points.

Only proved that 2010 trips are always sufficient - 5 points.