Consider a row of $15$ piles of bricks. There is a total of 75 bricks, all identical. The number of bricks per pile varies across the piles. For instance, the distribution of bricks per pile might be as follows:
$$
6\ \ 4\ \ 5\ \ 2\ \ 3\ \ 0\ \ 8\ \ 6\ \ 7\ \ 10\ \ 2\ \ 2\ \ 2\ \ 11\ \ 7
$$
The piles are numbered consecutively from 1 to 15 going from left to right. $P_i$ denotes the number of bricks in pile $i$. For instance, in the above example $P_6 = 0$.
Given a pile number $i$ and a number of bricks $b \leq t_i$, we may move $b$ bricks from pile $i$ to one of the piles adjacent to it, i.e. to pile number $i-1$ or $i+1$ (unless $i = 1$ or $i = 15$, in which case only a single pile is adjacent to pile $i$). We may not skip piles, for instance, if we wish to move a certain number of bricks from pile $5$ to pile $3$, we must first move the desired number of bricks to pile $4$, and then move the same number of bricks from pile $4$ to pile $3$.
The act of moving a bunch of bricks from one pile to an adjacent one, as described in the previous paragraph, is called "a move". So, for instance, one single move might be moving $5$ bricks from pile $9$ to pile $10$.
What is the minimum number of moves required to make all piles have the same number of bricks, namely $5$ bricks?
Hint: In a minimal sequence of moves bricks don't get moved between two adjacent piles more than once.
In addition to solving the puzzle, I'd like also to understand why the hint is valid. I get it intuitively – the hint, that is – sort of, but I don't see how to prove it, not even informally, let alone formally. Thanks.
Best Answer
Based on the hint, a maximum of $14$ moves are required, because there are just $14$ gaps to move bricks across and you only move bricks across each gap once. If we start with all the bricks in one pile, it should be obvious that $14$ moves are necessary, so we have the answer. The challenge is proving that the hint is correct in that you can always avoid moving blocks across a gap more than once in a solution.
We prove the more general statement that the $n$ pile problem can be solved in $n-1$ moves by induction on the number of piles. Clearly the $2$ pile problem can be solved by $1$ move. Now assume that we have proven that all problems up to $k$ piles have been shown to be able to be solved in $k-1$ moves and we consider the $k+1$ pile case. If either end has more than $5$ pieces in it, we can move the excess inward and we have a $k$ pile problem, which can be solved in $k-1$ moves. Adding the move we have made, we have solved the $k+1$ pile problem in $k$ moves. If either end has less than $5$ pieces and the neighboring pile has enough to make $5$, we can move enough pieces to the end pile to make $5$ and again we have a $k$ pile problem left. The remaining problem is if the two piles at each end total less than five bricks each. We will be done if we can show there are a pair of piles $i$ and $i+1$ that we can move bricks so we have $5i$ bricks in piles $1$ through $i$. This leaves $5(k-i+1)$ bricks in piles $i+1$ through $k+1$ and now we have two problems, one with $i$ piles and one with $k-i+1$ piles. These can be solved in $i-1$ and $k-i$ moves respectively, so the total number of moves is $k$ again.
Assign a number to each pile which is five times the pile number minus the total number of bricks in that pile and all the ones of lower number. This represents how many more bricks are needed to complete all the piles up to this one. We said that there were less than five bricks between piles $1$ and $2$, so pile $2$ gets a number that is at least $6$. A pile with more than five bricks will decrease this number and one with less than five bricks will increase it. Pile $k+1$ will get $0$ because we have the right number to satisfy all the piles. Pile $k-1$ will get at most $-6$ because at least $6$ bricks must be moved to the last two piles. If there is a pile where the number is zero, we already have two separate problems and can solve them in a total of $k-1$ moves. Otherwise, the pile where the number goes negative has enough bricks to give the pile to its left to make the left pile have a number of zero, thus splitting the problem.
For an example, I modified yours to make the end piles short. I didn't make them so short tat we can't just fill up the end, but it still works. We have $$\begin {array} {l r r r r r r r r r r r r r r r} \text{pile}&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15\\ \text {bricks}&4&4&5&2&3&11&8&6&7&10&2&2&2&4&4\\ \text {number}&1&2&2 &5&7&1&-3&-4&-6&-11&-8&-5&-2&-1&0 \end {array}$$ so we can move on brick from pile $7$ to $6$ and we have split the problem. In all the cases we have shown that we can move bricks across one gap and not have to move any across that gap again.