What is known in general about the liquid transfer problem?

Question

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.

Answer 1

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.

Answer 2

Note: I misread the question, so I mistakenly answered the variant where you have an unlimited source of water/vodka to fill buckets from. My answer still applies in the case where there is one bucket whose volume is at least as large as the sum of the others, and the initial contents of the buckets is enough to fill the big bucket.

---

It is easy to describe which positions are reachable starting from the empty state. Clearly, you can only produce amounts of water which are multiples of the gcd of the bucket sizes, and every reachable configuration has at least one empty or full bucket. These two conditions completely classify reachable configurations, as I showed in this MSE anwwer. The idea of the proof is this. Suppose the bucket volumes are $b_1,\dots,b_n$. A configuration is described by an element of $$ (x_1,\dots,x_n)\in (\mathbb Z/b_1\mathbb Z)\times \dots \times (\mathbb Z/b_n\mathbb Z) $$ where $x_i$ is the content of bucket $i$. In this view, a full bucket is considered equivalent to an empty bucket, which is fine because we can easily convert between empty and full.

For all $i,j\in [n]$, as long as there exists $k\neq i$ such that $x_k\equiv 0$, there exists a sequence of moves which changes the contents of bucket $i$ to $x_i+b_j$, and leaves all other buckets unaffected.

Let $d=\gcd(b_1,\dots,b_n)$. Using the method described above, you can change the contents of each bucket by arbitrary multiples of $d$. Provided the target configuration $y$ has at least one empty (or full) bucket, this means that in the case $d=1$, we have shown that $y$ is always reachable.

For general $d$, we only need to consider the residuals of two configurations modulo $d$ to determine whether or not you can reach one from the other. We have reduced the problem to analyzing residual configurations of the form $$ (r_1,\dots,r_n)\in (\mathbb Z/d\mathbb Z)^n $$ The legal moves in this framework are as follows:

• Filling or emptying bucket number $i$ replaces $r_i$ with $0$.

• Pouring between buckets $i$ and $j$ replaces $r_i$ and $r_j$ with $r_i+r_j$ and $0$. For a single pouring, the merged residual $r_i+r_j$ can end up in either bucket $i$ or $j$, but with additional pourings, you can control which of $i$ and $j$ it ends in.

With this insight, it is now easy to give a short description of all reachable configurations. Starting from $(x_1,\dots,x_n)$, you can reach $(y_1,\dots,y_n)$ if and only if $y_k\equiv 0\pmod {b_k}$ for some $k\in [n]$, and there exist disjoint subsets $E_1,\dots,E_n\subseteq [n]$ for which $$ y_i\equiv \sum_{j\in E_i} x_j\pmod { d } $$

For example, with $n=5$ and $d=3$, if the initial configuration is $(2,1,1,0,0)$, then we can only reach arbitrary permutations of $$ (2,1,1,0,0), (1,1,0,0,0), (2,1,0,0,0),(1,0,0,0,0),(0,0,0,0,0),\text{ and } (2,2,0,0,0) $$ together with anything attained by adding a multiple of $3$ to any coordinate, provided coordinate one remains zero.

In the case $d=2$, we can give an exact description of reachable configurations. Starting from a configuration with $m$ odd buckets, you can reach any configuration with $m'$ odd buckets provided $m'\le m$. However, I think that in general the disjoint-subset-sum condition cannot be simplified.