## Problem #004 - solvability of the water buckets

232

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! ### Problem statement

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:

• completely fill up bucket $$i$$ so that it holds $$c_i$$ litres of water;
• completely empty bucket $$i$$ so that it now holds $$0$$ litres of water;
• move water from bucket $$i$$ to bucket $$j$$, until bucket $$i$$ becomes empty or bucket $$j$$ becomes full, whatever happens first.

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$$.

If you need any clarification whatsoever, feel free to ask in the comment section below.

### Solution

You can read the solution here to compare with your own solution.