In this post I talked about the riddle of the water buckets. Now I challenge you to prove that in some situations it is impossible to solve it!
Follow me on Twitter, where I write about Python, APL, and maths.
You have \(n\) buckets, each bucket with capacity for \(c_i\) litres of water, \(i = 1, \cdots, n\). You want to manipulate the buckets in such a way that one of them holds exactly \(t\) litres of water, knowing that the only moves you can do are:
Prove that, if \(t\) is not a multiple of the greatest common divisor of the \(c_i\), \(i = 1, \cdots, n\) then it is impossible for a single bucket to hold exactly \(t\) litres of water.
For example, if the buckets have capacities \(4\) and \(6\) and \(t = 3\), then you can't perform the moves above to get exactly \(3\) litres of water into one of the two buckets as the greatest common divisor of \(4\) and \(6\) is \(\gcd(4, 6) = 2\) and \(3\) is not a multiple of \(2\).
Give it some thought... and give it an actual shot! Take out a piece of paper and a pencil and get your brain working!
If you need any clarification whatsoever, feel free to ask in the comment section below.
A possible solution is to consider a clever invariant that applies to the amount of water that each bucket is holding at any point in time. To make this easier, let's call \(d\) to the greatest common divisor of the \(c_i\), \(i = 1, \cdots, n\) (\(d = \gcd(c_1, \cdots, c_n)\)). Let's also say the amount of water in bucket \(i\) is \(w_i\). We will show that, regardless of the moves we make, \(w_i\) is always a multiple of \(d\) for all \(i\) (which we write \(d | w_i\) for _"\(d\) divides \(w_i\)"_).
At the start all buckets are empty, so \(w_1 = \cdots = w_n = 0\) and \(0\) is a multiple of \(d\) so that is that. Now we show that the three moves above preserve this property that \(d | w_i\ \forall i\).
We showed that no matter what we do, the amount of water in a bucket is always a multiple of \(d\), so if \(t\) is not a multiple of \(d\) this means we can never have a single bucket holding \(t\) litres of water...
Don't forget to subscribe to the newsletter to get bi-weekly problems sent straight to your inbox and to add your reaction below.
Thanks for reading this far! If you would like to show your appreciation for my work and would like to contribute to the development of this project, consider buying me a slice of pizza 🍕.