Today we will look at a brainteaser puzzle: "how to measure out exactly 1 liter of water using a 3-liter jug and a 5-liter jug." We will analyse this puzzle to see that, despite its innocent look, this puzzle has a close connection with the linear Diophantine equation.
Consider the following cheeky little puzzle.
A measuring liquid puzzle. Suppose you have a 3-liter jug and a 5-liter jug, how would you measure out exactly 1 liter of water?
Let us analyse this puzzle together.
We will consider all possible measuring operations and we want to find out how the amount of water in the jugs changes over time when we are filling and pouring water from jug to jug.
Suppose that the $3$-liter jug is currently holding $a$ liters of water and the $5$-liter jug holding $b$ liters, we then have 8 possibilities for our next measuring operation:
- Case 1:pouring all the water in the $3$-liter jug out: the amount of water in the two jugs will change to $$(a,b) \to (0,b)$$
- Case 2:pouring all the water in the $5$-liter jug out: the amount of water in the two jugs will change to $$(a,b) \to (a,0)$$
- Case 3:filling the $3$-liter jug to the full: the amount of water in the two jugs will change to $$(a,b) \to (3,b)$$
- Case 4:filling the $5$-liter jug to the full: the amount of water in the two jugs will change to $$(a,b) \to (a,5)$$
- Case 5: $a+b \leq 5$pouring all the water in the $3$-liter jug into the $5$-liter jug: the amount of water in the two jugs will change to $$(a,b) \to (0,a+b)$$
- Case 6: $a+b \leq 3$pouring all the water in the $5$-liter jug into the $3$-liter jug: the amount of water in the two jugs will change to $$(a,b) \to (a+b,0)$$
- Case 7: $a+b \geq 5$pouring the water in the $3$-liter jug into the $5$-liter jug until it is full: the amount of water in the two jugs will change to $$(a,b) \to (a+b-5,5)$$
- Case 8: $a+b \geq 3$pouring the water in the $5$-liter jug into the $3$-liter jug until it is full: the amount of water in the two jugs will change to $$(a,b) \to (3,a+b-3)$$
The amount of water contained in the jugs will initially start with the value $(0,0)$, and after each step of measuring operation, the value $(a,b)$ will change into one of the following 8 possible values $$(0,b), ~~(a,0), ~~(3,b), ~~(a,5),$$ $$(0,a+b), ~~(a+b,0), ~~(a+b-5,5), ~~(3,a+b-3).$$
Since this value changes only involve addition and subtraction of 3 and 5, we can easily show that
The amount of water in each of the jug is always a number of the form $3 x + 5 y$ where $x$ and $y$ are two integers.
With this observation, our puzzle is reduced to the problem of solving the following linear Diophantine equation $$3x + 5y = 1.$$
This equation has infinitely many integer solutions. It implies that there would be many possible answers to our original puzzle.
First solution: We can easily see that $x=2$, $y=-1$ is a solution to the equation $3x+5y=1$ as $${\bf 3} \times 2 - {\bf 5} \times 1 = 1.$$
Using this solution, we can devise an answer to our puzzle as follows: to get 1 liter of water, we fill the 3-liter jug to the full twice and pour it out to the 5-liter jug making it full once.
So here is an answer to our puzzle:
 |
| ${\bf 3} \times 2 - {\bf 5} \times 1=1$: Filling 3-liter jug to the full twice and pouring out to 5-liter jug making it full once, we get 1 liter remaining. |
Second solution: Another solution of the equation $3x+5y=1$ is $x = -3$, $y=2$ as $${\bf 5} \times 2 - {\bf 3} \times 3 = 1.$$
Corresponding to this solution, we fill the 5-liter jug to the full twice and pour it out to the 3-liter jug making it full three times.
Here is the second answer to our puzzle
 |
| ${\bf 5} \times 2 - {\bf 3} \times 3=1$: Filling 5-liter jug to the full twice and pouring out to 3-liter jug making it full three times, we get 1 liter remaining. |
We have seen that our measuring liquid puzzle has a close connection with the Diophantine equation $$3x+5y=1.$$ Let us stop here for now and in the next post, we will see that our puzzle also has a connection with the regular polygon construction problem. See you next time.
Homework.
1. Using induction, prove that the amount of water in each jug is always a number of the form $3 x + 5 y$.
2. You have a 5 liter jug and a 7 liter jug. How would you measure out exactly 1 liter of water?
3. You have a 5 liter jug and a 7 liter jug. How would you measure out exactly 3 liters of water?
4. You have a 6 liter jug and a 8 liter jug. How would you measure out exactly 3 liters of water?
4. You have a 6 liter jug and a 8 liter jug. How would you measure out exactly 3 liters of water?
5. Go to google.com and search for linear Diophantine equation.