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)
(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>
re(4): Still stumped original solution p1 - spoiler
