1. My TSR
  2. News

Dr Georgiou's maths challenge: can you fill a jar with water?

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? 

5L jug 3L jug

There’s actually more than one solution; here are a couple of examples...
 

Solution 1

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.

Or

Solution 2

Fill the 5L jar and pour it in the 3L one until is filled. Then empty the 3L one. 
Pour the remaining 2L from the 5L into the 3L. Refill the 5L one and use 1L from it to fill 3L jar. Then empty the 3L jar. 

At this point you have 4L in the 5L jar and an empty 3L jar. One last time pour water from the remaining 4L in the big jar until the small one is filled. Then only 1L of water is remaining in the 5L jar.

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. 

The theorem

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. 

One solution (x,y) is given by x =5, y = -5 since 5 = 45 -40) = 9x5-8x5. To actually solve it, we must fill the 9L jar 5 times overall. 

So we iterate the following: Fill the 9L, and use it to fill the 8L. Then empty the 8L and pour the remaining 1L in it. 

Fill the 9L end use it to fill the remaining 7L in the 8L jar. Empty the 8L jar. Now you have 2L in the big one and 0 in the smaller jar. Iterate this procedure 3 more times until you have 5L in the big jar.

 

 

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.

This can take a lot of time to find. So we do a little trick. Notice 24 x 3 = 72 and 14 x 5 is 70. Therefore we have 24 x 3 + 14 x (-5) = 2. 

Now multiply left and right by 3, so we have the desired 6 on the right hand side. The equation becomes 24 x 9 + 14 x (-15) = 6.

So we need to fill the 24L jar nine times, and empty the 14L 15 times! That seems like a lot so perhaps we missed some smaller solution. But in any case, we start trying and see what happens. Worst case scenario, we do what the solution tells us!

Let’s see what happens after the first few steps. Fill 24L, and pour in the 14L. Then empty that. 

We have 10L in the big, and 0 in the second. Now pour the 10L in the 14L, and fill the big one again. 

Pour another 4L in the small one and empty it. So now we have 20L in the big one and 0 in the small. 

Pour in the small one one more time (without refilling the 24L first) and empty it. Now you have 6 L in the big one. 

So we did miss a smaller solution! We filled the big one two times and emptied the small one three, so 24 x 2 + 14(-3) = 48 - 42 = 6.

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. 

In the problems we show that if you have a solution you can use it to get that quantity (this needs a general proof that it always works). 

For the reverse, one needs to show that any filling or emptying of jars that leads to a correct quantity and corresponds to a solution to the equation.

 

Article by TSR User on Thursday 15 February 2018