Friday, October 5, 2007

Solution to Empty the Bucket Puzzle

This is the solution for the Puzzle --Empty the Bucket Puzzle .

For those who haven't tried the puzzle. First give it a try at Empty the Bucket Puzzle

First observe that a very special thing happens when you work with just two buckets, where one has an even quantity and one has an odd quantity. Because there are just two unequal buckets, there's just one move possible: Pour water from the bucket with more water into the bucket with less water. Note that the move preserves the property that one bucket is even and the other one is odd.

What happens if we just keep doing this? Since there are a finite number of states, we must eventually repeat a state we've seen before. In fact, the first repeated state must be the original configuration. This is because for any configuration in this sequence, there is a unique prior one -- it's the one obtained by moving half of the even bucket's water to the odd bucket.

If the cycle is of length n, then by making n-1 moves, we reach the state "preceeding" the initial one. So if we were in the state (a,b), where a is even and b is odd, then we can get to the state (a/2, b+a/2).

With this under our belt, let's look at a little more general case. Suppose one of the buckets has an odd quantity of water, and the other two have an even quantity of water. Call this the odd-even-even case. We'll show how to increase the size of the odd bucket, while preserving the evenness of the other two. Eventually one of the even buckets must be empty. Let the quantity of water in the buckets be (a, b, c) where a is odd and b and c are even. First if neither b nor c are a multiple of 4, then make one move among them so that one of them is a multiple of 4. Now, by relabeling buckets we can assume without loss of generality that we have three buckets (a, b, c), where a is odd b is a multiple of 4, and c is even. Now we make a backwards move between a and b. The three buckets are now (a+b/2, b/2, c). We still have one odd and two even buckets, and we've grown the odd bucket. By repeating this algorithm one of the even buckets must eventually become empty. This solves the odd-even-even case.

What about the rest of the cases? The odd-odd-odd case becomes odd-even-even (solved above) after any move is made. The other cases are proven by induction. In the even-even-even case we simply divide all the bucket sizes by 2 and solve the smaller problem. The even-odd-odd case is solved by first making a move among the two odd buckets, which leads to the (already solved) even-even-even case.


1 comment:

  1. I like this blog it’s very informative and attractive also. Thanks to author for this post it’s very easy to understand. Bucket Elevator


Subscribe via email

Enter your email address:

Delivered by FeedBurner