Dr Nicos Georgiou is a lecturer in the School of Mathematical and Physical Sciences at the University of Sussex. Here he presents his latest TSR maths challenge. Can you crack it?
Some of the many classical puzzles involve two or three (or even more!) jars of different sizes.
The goal is simple: the solver must create an exact quantity of water in one of the jars.
Here's an example:
You have an infinite supply of water, a 5L jar and a 3L jar. You can empty a jar completely anytime you like and you can pour water from one jar to the other. How will you measure exactly 1L of water?
There’s actually more than one solution; here are a couple of examples...
Fill the 3L jar and pour it in the 5L one. Then fill it again and pour it in the 5L until it fills up. Then, there’s exactly 1L of water in the 3L jar.
Fill the 5L jar and pour it in the 3L one until is filled. Then empty the 3L one.
So, not only can we find solutions; we can find many solutions. If someone constructs the problem correctly, that is.
The question above can be reordered in all sorts of ways. We could ask for 1L, 2L, 3L, 4L or 5L to be measured – all are possible values that could be found (try it!).
But here’s an extra layer of difficulty. Can we decide if the problem has a solution, before we even attempt to solve it?
Let's try with some more puzzles.
First, decide whether the puzzle is solvable. If it is, find a way to do it.
You always have an infinite supply of water, you can empty a jar completely anytime you like and you can pour water from one jar to the other
a) Jar 1: 9L, Jar 2: 8L. Quantity that needs measuring: 5L
b) Jar 1: 9L, Jar 2: 8L. Quantity that needs measuring: 6L
c) Jar 1: 12L, Jar 2: 8L. Quantity that needs measuring: 6L
d) Jar 1: 24L, Jar 2: 14L: Quantity that needs measuring: 6L
|More on TSR:
More maths puzzles: the proof is trivial
Ask a maths question in the maths forum
Year 12: maths help thread
Can it be solved?
There’s a simple trick to deciding whether there is a solution: look at the g.c.d. (the greatest common divisor or greatest common factor) of the jar capacity.
In the example with 5L and 3L, we are looking at distinct prime numbers, therefore their greatest common divisor is 1.
And we can achieve all possible values higher than 1L (which can be viewed as achieving all integer multiples of the value 1 = g.c.d.(3,5)).
Looking at the puzzle in our introduction, the first solution we considered corresponds to the following relation:
g.c.d.(3,5) = 1 = 2 x 3 – 1 x 5
This essentially means the 3L jar needs to be filled twice and the 5L emptied once.
The second solution of our example corresponds to:
g.c.d.(3,5) = 1 = 2 x 5 – 3 x 3
So the 5L jar needs to be filled twice and the 3L need to be separated three times from that. We did that, but the 3L jar was only emptied twice.
In the end, the question comes down to this. We can measure L litres of water with jars that have capacity A and B litres when the equation L = Ax + By has integer solutions (x,y).
This is a linear Diophantine equation, linear because there are no exponents or other functions involved, Diophantine because we are only interested in integer solutions.
The fact that when L =g.c.d. (A, B) the equation always has a solution is a consequence of Euclid’s algorithm.
We assume L, A, B are known integers. The equation L = Ax + By has infinitely many integer solutions x, y if (and only if) L is an integer multiple of the g.c.d.(A,B).
With this theorem, we can decide whether the problems given are solvable. Then we must find one solution x, y to the equation and use that to help us find a solution to the problem. Can you argue that if the Diophantine equation has no solution, then we cannot actually obtain the requested quantity of water?
solution to question a
a) The g.c.d of 8 and 9 is 1, therefore we can solve the equation 5 = 9x + 8y as 5 is a multiple of the g.c.d.
solution to question b
b) Exactly as in (a) but we do the iteration step once more.
solution to question c
c) The g.c.d.(12, 8) = 4 and 6 is not a multiple of 4. So therefore we cannot have a solution here. We can only separate multiples of 4L.
solution to question d
d) The g.c.d. (24,14) = 2. Since 6 is a multiple of 2, a solution exists. This is slightly trickier to find; one needs to find multiples of 24 that are 6 away from multiples of 14.
Oh, and as for that earlier question about Diophantine equations. Well, the complete argument would take more than a page to write properly...
But here's the short version
The answer is 'yes'. If one can get the requested quantity of water then they did so by filling or emptying the A and B jars.