Empty one of three buckets by doubling pours

Question

Three buckets contain whole numbers of litres, say a, b and c, all positive, with plenty of spare capacity. The only allowed move is a doubling pour: choose two buckets X and Y and pour from X into Y exactly as much as Y currently holds, so Y doubles and X loses that amount (X must contain at least that much).

Prove that, whatever the starting amounts, a sequence of doubling pours can always empty one of the buckets.

Accepted Answer

Yes. The strategy makes the smallest bucket's content strictly decrease each round, so it must reach zero. Set up. Suppose a is at most b, which is at most c. Divide: b = qa + r, with 0 at most r less than a. Write q in binary as a sum of powers of two, q = e0 + 2 e1 + 4 e2 + ... with each ei equal to 0 or 1. One round. Perform pours into bucket A (the smallest), one for each binary digit, starting from the lowest: - At step i (i = 0, 1, 2, ...), bucket A holds 2 to the i times a. If the digit ei is 1, pour into A from B; if ei is 0, pour into A from C. Either way A doubles. After all the ste…

Empty one of three buckets by doubling pours

Your answer

Discussion

Learn the concepts

Related questions