Problem #04 - solvability of the water buckets

This post's problem is a follow-up from this earlier post in which I talk a little bit about the problem of the water buckets and describe how I wrote a program to solve it. If you spot any mistakes here (or there) please let me know!

Problem statement:
Given $n$ buckets of capacities $c_1, \cdots, c_n$, prove that if the target value $t$ is not a multiple of $d = \gcd{(c_1,\cdots,c_n)}$ then the problem is unsolvable.

Show that if all quantities in all buckets are multiples of $d$, then after one single move, that still holds.

Solution:
We will show that, regardless of the sequence of moves, all values in all buckets are - at all times - multiples of $d$. Let $w_i$ denote the value of bucket $i$. It is easy to see that in the beginning we have that each bucket has $w_k = 0 = \sum_{i=1}^n 0\cdot c_i$ and thus our property holds for the initial configuration.
Now consider that for each bucket $k, w_k = \sum_{i=1}^n a_{k,i}c_i$ (i.e., all values are multiples of $d$). Remember there are three types of moves: emptying a bucket (which sets $w_k = 0 = \sum_{i=1}^n 0\cdot c_i$), filling a bucket (which sets $w_k = c_k$) and pouring bucket $k$ into bucket $p$. For the third movement, one of two things happens:

• The contents of bucket $k$ all fit into bucket $p$, and thus $w_k = 0, w_p = \sum_{i=1}^n (a_{k,i} + a_{p,i})c_i$
• Bucket $p$ wasn't sufficiently empty and thus it filled, meaning $w_p = c_p$ and $w_k = \sum_{i=1} a_{k,i}c_i - \left(c_p - \sum_{i=1}^n a_{p,i}c_i \right) = \sum_{i=1}^n (a_{k,i} + a_{p,i})c_i - c_p$

That is, the fact that all values are multiples of $d$ is preserved by the moves allowed to solve the problem and hence the problem is unsolvable if $t$ is not a multiple of $d$.

Let me know what you think!

-RGS