2^m marbles in multiple boxes.

Question

Let m be a non-negative integer. Suppose $2^m$ marbles are separated into several boxes. At each step we are allowed to do the following operation: Pick two boxes, say box A with p marbles and box B with q marbles and p ≥ q, and then remove q marbles from box A and put them in box B. Prove that it is possible to put all the marbles into one box.

Answer 1

We do an induction on $m$. Suppose the result is true for $2^m$ marbles. We show it is true for $2^{m+1}$ marbles.

There is an even number of boxes that have an odd number of marbles. For any two such boxes, a legal move makes the numbers even in both. So there is a combination of legal moves such that we end up with an even number of marbles in each box.

Once this is done, glue the marbles in each box together into pairs, and call such a glued pair a "marble." We now have $2^m$ "marbles." Apply the induction hypothesis.