The Empty Bottle

  1. Consider three bottles of water. The first contains 1 ml, the second 5 ml and the third 10 ml. Each bottle can contain the total volume (16 ml in this case). The rule is that we can pour the content of a bottle into another one only if we can double the content of the second one. For example, we can pour 5 ml from the third bottle into the second one, or 1 ml from either of the last two bottles into the first one. Show that it is possible to get very easily and quickly an empty bottle. What is the minimum number of pourings necessary?
  2. Repeat for volumes of 3, 8, and 23 ml.
  3. Repeat for large volumes of 37, 91, and 203 ml.
  4. Repeat for positive integer volumes of a, b, and c ml, c>b>a. Can an empty bottle always be reached? What requirements are on a, b, and c?

Source: Reader Philippe Fondanaiche.

Solutions were received from Philippe Fondanaiche, Arturo Pascalin, Rich Polster, and William Beall:
  1. Three pourings are needed: 
      1    5    10
----------------
  2    4    10
  4    4     8
  0    8     8
  2. Four pourings are needed: 
      3    8    23
----------------
  3   16    15
  3    1    30
  2    2    30
  0    8    30
  3. Seven pourings are needed, according to Arturo: 
     37   91   203
----------------
 37  182   112
 37   70   224
 74   70   187
148   70   113
 35   70   226
 70   70   191
  0  140   191
  4. Craig Gentry sent the following analysis:

    Since there are no other takers, here's a proof that you can empty a bottle for any a<=b<=c. Assume that, given a, b and c, the smallest amount we can have in a bottle (through any sequence of pourings) is x, which is greater than 0. Let y<=z be the amounts in the second and third bottles, and let k = [y/x], where [] is the greatest integer function. Put k in binary (1's and 0's), and, reading k from right to left, pour from the second bottle if there's a 1 and pour from the third bottle if there's a 0. If x divided y, then at the end of this process, the second bottle will be empty; otherwise, the second bottle will ultimately have less than x, creating a contradiction.

    As an example of how this works, take 3, 8, 23. Suppose we assume that 3 is the smallest amount we can ever have in a bottle. Now, k = [8/3] = 2, which is 10 in binary. Reading k from right to left, we encounter a 0 first, meaning we pour from the third bottle, getting 6, 8, 20. Since a 1 is next in the binary expression, we pour from the second bottle next, getting, 12, 2, 20 - 2 being less 3. Now, we can start anew with the triplet 2, 12, 20. This time, k = [12/2] = 6, which is 110 in binary. So we pour from the third bottle - 4, 12, 18 - then the second - 8, 8, 18 - then again the second - 16, 0, 18. Of course, this is not the fastest way, but it always works.
    -Craig Gentry ts208@is5.nyu.edu

Mail to Ken