MathDB

2011 storage buildings are connected by roads so that it is possible to reach any building from any other building, possibly using multiple roads. The buildings contain

x_1,\dots,x_{2011}

kilogram of cement. In one move, it is possible to relocate any quantity of cement from one building to any other building that is connected to it. The target is to have

y_1,\dots,y_{2011}

redistributed across storage buildings and

x_1+x_2+\dots+x_{2011}=y_1+y_2+\dots+y_{2011}.

What is the minimal number of moves that the redistribution can take regardless of values of

x_i

and

y_i

and of the road plan? (Author: P. Karasev)

11.4

Problems(1)