Three Gallon Jug and 5 Gallon Jug [duplicate]

One of the classical puzzles is pouring water into the 5 gallon jug so there is 4 gallons of water remaining. This was popularized by Bruce Willis in "Die Hard with a Vengeance". I was wondering however, if there was a possible way to complete the puzzle using a 3 gallon jug and a 7 gallon jug to still get the 4 gallons.

If so, what other combinations of jugs could you use to still get the same four gallon requirement?

Edit: When doing the 4 gallons remaining from the 7 gallon jug, you must have 1 gallon of water left in the three gallon jug.

• getting 4 gallons with a 3 and a 7 is laughably easy, empty the full 7 gallon into the 3 gallon until the 3 is full, you have $7-3=4$ remaining in the 7 gallon jug – ratchet freak May 15 '14 at 14:09
• I think this question would work a little better if it had more info for those unfamiliar with the original problem (and who, sadly, lack the time to go watch DH3 :p) – Jaydles May 15 '14 at 14:11
• @ratchetfreak I forgot the second part of the puzzle. – Young Guilo May 15 '14 at 14:37
• If in your edit you mean a little before having 4 in the 7 gallon jug you must have 1 in the 3 gallon jug you can do that. Fill the 7 from the 3 twice, filling the 3 from the tap five times, and you have 1 in the 3. Move the 1 to the 7, refill the 3, dump it in the 7 and you have 4. Otherwise I don't understand what you are saying. – Ross Millikan May 20 '14 at 15:53
• Go to the grocery store and buy a 1 gallon water container.... – PopularIsn'tRight Nov 11 '14 at 0:05

4 Answers

Your added constraint of having 1 gallon left in the small jug makes the puzzle impossible.

The only available moves are

• fill a jug from the well, filling it completely
• empty a jug into the well, emptying it completely
• pour one jug into another, until either one jug is completely empty or the other jug is completely full

Since these moves leave you with at least one jug either completely empty or completely full, nothing among these moves lets you end up with both jugs partially filled.

For 7 and 3 wanting 4, just fill the 7 and fill the 3 from it, leaving 4.

Say you had 7 and 3 and want 2.
Fill the 7
fill the 3 from the 7, leaving 4
empty the 3
fill the 3 from the 7, leaving 1
empty the 3
put the 1 in the 3
fill the 7
fill the 3 from the 7, leaving 5
empty the 3
fill the 3 from the 7, leaving 2

Basically you need the desired quantity to be less than the large jug and to have the desired quantity to be a multiple of the least common multiple of the jug volumes. The algorithm is simple: fill the large jug, keep filling the small jug from it, refill the large jug when you must, and you will get there. You are finding a solution to Bézout's identity My solution is 2*7-4*3=2 The solution in the comments is 3*3-1*7=2 Note that if you subtract these two equations you get 3*7-7*3=0

• or fill 3 empty in 7, fill 3 again and empty into 7... – ratchet freak May 15 '14 at 14:28
• @ratchetfreak: yes, you can always go either way around. I will find a better example. Even here, you could fill the 3 three times, filling the 7 from it, and be left with 2. – Ross Millikan May 15 '14 at 14:29
• ...fill 3 empty into 7 until full -> 2 remains in 3 – ratchet freak May 15 '14 at 14:30

for 2 jugs that can contain $x$ and $y$ you can get any multiple of $GCD(x,y)$ between $0$ and $max(x,y)$ using the algorithm that @Ross described.

You can understand this by creating a new unit so that $1 \text{ unit} = GCD(x,y)$ gallons, and now you have 2 jugs with $\frac x {GCD(x,y)} = x'$ and $\frac y{GCD(x,y)} = y'$ and because you can't take out fractional units it means that you alway have a multiple of $GCD(x,y)$ in your jugs.

Fill the 7 gallon jug, then fill the 3 gallon jug using the water from the 7 gallon jug, repeat this step, now you have excactly 1 gallon left in the 7 gallon jug, and just simply pour that gallon of water over into the 3 gallon jug

• The goal of the puzzle is to have 1 left in the small jug and 4 left in the big jug. – Deusovi Jan 2 '16 at 2:23