The story of the water jug puzzle

You have two jugs with no markings on them, say 3 L and 5 L, and an endless supply of water. Can you measure exactly 4 L with just those two? You may only fill a jug, empty a jug, or pour from one into the other. A pour cannot stop partway: it ends when the source is empty or the destination is full. Still, with some cleverness, you can measure exact amounts with no markings at all.

Pulling out the difference

Here is a way to get 4 L from a 3 L jug (left) and a 5 L jug (right).

• Fill the right jug (right 5 L).
• Pour right into left (left 3 L, right 2 L). The left jug is full, so the pour stops.
• Empty the left jug.
• Pour the 2 L from right into left (left 2 L, right 0 L).
• Fill the right jug (left 2 L, right 5 L).
• Pour right into left. The left jug has room for only 1 L more, so 4 L stays in the right jug.

That is 6 moves. The trick is that filling one jug from a full one leaves the difference between the two capacities, and you keep reusing that remainder to build new amounts. Of this site's four preset puzzles, 3 L and 5 L to make 4 L takes 6 moves, 2 L and 7 L to make 5 L takes 2, and 3 L and 5 L to make 1 L takes 4. The program checks all of these minimums.

What decides the amounts you can make

Can you make any amount? No. With 4 L and 6 L jugs you can never get 3 L, because only even amounts such as 2, 4 and 6 ever turn up.

When the capacities are whole numbers, the amounts you can make are exactly the multiples of the greatest common divisor of the two capacities. The greatest common divisor is the largest whole number that divides both. For 4 and 6 it is 2. Any amount that is a multiple of it and fits in a jug can be made. In mathematics this follows from an idea called Bézout's identity. When the greatest common divisor is 1, as with 3 L and 5 L, every whole amount can be made.

On this site you can choose capacities and a target from 1 to 12 L. For every one of those combinations, the program searches all the states and confirms that the amounts you can make are exactly the multiples of the greatest common divisor. If your target cannot be made, the hint says so.

How old is the puzzle?

Puzzles of measuring with jugs of different sizes are said to have been known since the Middle Ages. A mathematics journal notes that the 17th-century mathematician Bachet included them in his book. Who first thought of them, and when, is not clear.

In 1939 a way of solving this kind of puzzle with a diagram was published in a mathematics journal, so the story goes. Take the amounts in the two jugs as coordinates, and the pouring steps become the path of a ball bouncing around a slanted, billiard-like table. The graph on the puzzle page works the same way: the horizontal axis is the left jug, the vertical axis is the right jug, and each arrow is one move.

How to think about it

• First ask whether it can be made at all. If the target is not a multiple of the greatest common divisor, no number of tries will help.
• Pour from a full jug to make a difference. Fill, then pour, and the difference between the capacities is left behind.
• Keep the remainder and use the other jug. Leave a remainder in one jug, and fill or empty the other to build a new amount.
• Emptying and starting over is allowed. Use Back or Reset and try as often as you like.

Stuck? Press the Hint button on the puzzle page. It gives the idea, then the greatest common divisor, then the next move. For targets that cannot be made, it tells you why.