10
$\begingroup$

In several puzzle books, I have seen the following kind of a problem: there are several containers that can hold up to certain amounts of liquid (these liquids are assumed to be infinitely divisible). Given certain initial amounts, it is asked whether a certain other configuration (often equal division among some of the containers) is possible to achieve. There are variations, such as being able to throw out some of the liquid or being near a source such as a river (that is infinite for all intents and purposes).

Here is a specific example from The Chicken from Minsk by Chernyak and Rose:

Besides chess playing and problem solving, drinking is and always has been the most common form of recreation in Russia. Vassily has acquired a $12$-liter bucket of vodka and wishes to share it with Pyotir. However, all Pyotir has is an empty $8$-liter bottle and an empty $5$-liter bottle. How can the vodka be divided evenly?

The condition is that, at each step, some container must either be emptied or filled to the brim; we cannot measure more precisely. One can identify at least three general problems, given the finite list of container sizes and an initial configuration:

  1. Given another configuration, produce a condition or algorithm for deciding whether it is achievable.
  2. If a configuration is achievable, determine a way of showing how to go from the initial configuration to this one.
  3. Count how many distinct achievable configurations exist.

What is known about this problem, perhaps in complexity or computability theory if not in number theory? While I have seen instances here and there, I am unaware of a name for the general problem and so am unable to begin searching for its related literature. One trivial observation is that, if the container sizes and initial amounts in each container are all multiples of an integer, then all amounts in all individual containers in all achievable configurations must be multiples of this integer; the contrapositive might be useful.

$\endgroup$
2

1 Answer 1

15
$\begingroup$

These are also known as 'decanting problems' or water pouring puzzles. There is a list of literature references in that Wikipedia article.

They're quite popular among puzzling aficionados, and it should come as no surprise that our sister site Puzzling Stack Exchange has a question about this topic: A general solution to the decanting problem? (aka jug-pouring, water-pouring). In particular, your question 1. can be answered by checking if the greatest common divisor of all bottles divides the target amount. The GCD of 8 and 5 is 1, so you can basically achieve all volumes which are a multiple of 1 (liter). One of the answers provides a partial algorithm to solve your question 2., and the other one a program to generate the necessary steps.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.