All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Empty the bucket (Posted on 2017-05-29)
You are in the desert and you have 3 buckets of water containing a,b,c liters respectively (a,b,c - positive integers).
You need an empty bucket for an unspecified purpose. Being in the desert you need the water and cannot just pour it away.
You have to pour the contents of one bucket into another one. But in any pouring, you must double the contents of the bucket which receives the water.
For example the sequence of bucket contents could be:

3 2 1
1 4 1
0 4 2

Now show that no matter what a,b,c are, you can always manage to empty a bucket under this constraint.

You may assume:
a>b>c

&
(capacity of each bucket)>(a+b)

Comments: ( Back to comment list | You must be logged in to post comments.)
 re(4): Still stumped original solution p1 - spoiler | Comment 10 of 12 |
(In reply to re(3): Still stumped by Steve Herman)

.This problem is described in an article Five Algorithmic Puzzles by Peter Winkler that appeared in the Gathering for Gardner.

The solution (slightly abridged):

â€¦start 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.<o:p></o:p>

If the cycle is of length n, then by making n-1 moves, we reach the state "preceding"   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).<o:p></o:p>

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.  <tbc>

 Posted by Ady TZIDON on 2017-06-04 14:37:20

 Search: Search body:
Forums (0)