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

Filed under: puzzle | Tagged: bucket, puzzle, transfer, water |

Navin, on September 8, 2008 at 12:19 pm said: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.)

dmr, on September 8, 2008 at 1:10 pm said:do you have a proof? (3,3) can go to (0,6) in one step, but 3+3 is not a power of 2.

Navin, on September 16, 2008 at 9:53 am said: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.

Navin, on September 16, 2008 at 10:16 am said: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).