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)
Problem
Source: Problem 4 of Russian Regional Olympiad 2011, grade 11 day 1
Tags: induction, combinatorics proposed, combinatorics
math_explorer
02.09.2011 16:41
2010 moves are clearly necessary. A simple example: let the first building be empty, let every other building contain 1 kilogram and be connected to only the first building, and let the target be to have the first building contain all the cement. To prove that 2010 moves suffice, we use induction to prove that if there are $n$ buildings then $n-1$ moves suffice. When $n = 1$ the result is obvious. The induction step: pick a building $B$ which is connected to just one other building $N$. Then, removing $B$ won't affect the property that we can reach any building from any other building. If $B$ has more cement than we want, move the excess cement to $N$ (one move) and apply the induction hypothesis to redistribute the cement among the remaining buildings ($n-2$ moves). If $B$ has less cement than we want, say $c$ kilograms less, apply the induction hypothesis to redistribute the cement among the remaining buildings, with a modified target in which $N$ receives $c$ extra kilograms ($n-2$ moves), then move the $c$ kilograms to $B$ (one move).
chaotic_iak
03.09.2011 11:58
math_explorer wrote: pick a building $B$ which is connected to just one other building $N$. How can you make sure that there always exists at least one building that is connected to only one other building?
math_explorer
03.09.2011 15:13
Oops, you can't always do that. I somehow thought the graph was always a tree. The proof still essentially works though, since you can always delete edges from a connected graph to get a tree, and a strategy on a graph with deleted edges isn't affected if you add the deleted edges back. (an $n$-vertex tree must have a vertex with degree 1 since the total degree is $2(n-1) < 2n$)