P-010 Tipping the Buckets

There are three buckets containing m, n, p integral units of water respectively. You can repeatedly perform the following step: transfer water from one bucket to another such that the amount of water in the other bucket is exactly doubled. For example, if m < n, transferring m units will result in the buckets containing m and n units ending up with 2m and n-m units. Each bucket has a sufficient capacity > m+n+p.
Show that it is always possible to get one bucket empty.

Note – this puzzle is harder than the older three bucket puzzle where the receipient bucket is to be filled to the brim.

Advertisements

4 Responses

  1. I’ve managed to solve a simpler sub-problem; which I think is interesting in its own right.

    For just two buckets (n and m) what are the conditions under which you can empty one bucket?

    (Answer: it is possible if and only if n + m = 2^k for some k.)

  2. do you have a proof? (3,3) can go to (0,6) in one step, but 3+3 is not a power of 2.

  3. Sorry.
    I missed pointing out an intermediate step where I was supposed to have said that without loss of generality assume that n and m are relatively prime. In other words, divide n and m by their LCM and then my statement is true, I believe.

    In your example, (3,3) becomes (1,1) and 1+1 = 2^1.

    I do have a proof, I think, but I need to collect my thoughts. So I’ll post that in a separate comment.

  4. Proof that (n,m) is solvable if and only if n+m = 2^k.

    Solvable here means that I can empty one bucket.

    Proof:
    1. n and m are relatively prime. If not, let G be the gcd of n and m. I can simply rename my units so that each new unit is G old units, then n becomes n/G, m becomes m/G and they are relatively prime. This is essentially the same problem as before with different units.

    2. If n = m, then n = m = 1 and the problem is solvable in 1 step. Stop.

    3. if n + m is odd then this problem is not solvable. Because last step of a solution requires you to have same amounts in both buckets. Stop.

    4. Hence, n and m are both odd (by combining #1 and #3)

    5. Without loss of generality, assume that n > m. Now pour from n to m. Now the buckets have n-m and 2m units.

    6. At this point, n-m and 2m do not have any common factors that are not a power of 2. This follows from #1, and proof is left as an exercise for the motivated reader.

    7. n-m and 2m are both divisible by 2. Hence we divide by 2. Repeat this process until at least one of them becomes odd.

    7. Go to step 2. Lather, rinse repeat.

    Points to note: Step #7 always divides by 2 at least once. This happens after each pouring. So we can guarantee that this process terminates at #2 or #3 after a finite number of steps. And we note that we have only ever divided by 2, so n+m must be a power of 2 (after we have divided by the GCD in step 1).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: