Moving half of the nuts

An even number of nuts is divided into three nonempty piles. In each step, we are allowed to take half the nuts from a pile with an even number of nuts, and put them on another pile. Can we always reach a point where exactly half of the nuts belong to one pile?

For example, if we start with $(3,5,6)$, we can transform as $(3,5,6)\rightarrow (3,8,3)\rightarrow (3,4,7)$, and now the last pile has half of the nuts.

Note that in each step, some pile of nuts must be even, so we can keep moving. Moreover, we will never empty a pile.

Solution 1:

The answer is yes and here is how (I got the idea from Shooter's comment above):

Step 1: If you are given three even piles of nuts (otherwise go to step 2): Choose one pile and take nuts from it as long as you can (until the number of nuts is odd). Put them wherever you like.

Step 2: You now are in the situation even (pile A), odd (pile B), odd (pile C) (up to changing the order). Now, you cut pile A into half as often as you can. Put all of the nuts on pile C except in the last step in which you put them one pile B. So that now pile B is the only one with an even number of nuts.

Step 3: Go back to Step 2 (with A and B reversed) unless pile B has precisely double the size of pile A. In that case go to Step 4.

Step 4: You arrived at numbers of the form (x,2x,sum-3x). Cut B and put it on C, then cut C and put it on A to get (sum/2,x,sum/2-x).

For this algorithm to work, we have to argue, why indeed we get to step 4 at all: If we look at our loop, it is clear that the sum of the nuts in piles A and B is non-increasing and so there comes a point where it will be constant for all eternity (nothing goes to C any longer). If the loop never ends the numbers would then behave like this:

$$(m,2n) \to (m+n,n) \to (\frac{1}{2}m+\frac{1}{2}n,\frac{1}{2}m+\frac{3}{2}n) \to (\frac{3}{4}m+\frac{5}{4}n,\frac{1}{4}m+\frac{3}{4}n)\to ...$$

In this sequence it is easy to see that the difference between one entry and the same entry two steps later is always of the form $\pm 2^{-k}(m-n)$ with $k$ increasing with each step (it is a geometric sum). But all the numbers are integers so that $2^{-k}(m-n)$ must be an integer for all $k$. Therefore, $m=n$!

I hope I did not miss anything and this is correct.