1

We know that classical puzzle of getting 4 liters from 2 jugs of 3 liters and 5 liters capacity. (or was it gallons?)

But what about other volumes? And what if the jugs had different volumes?

For instance, if you had a 7 liter jug and an 11 liter jug how can you get 9 liters exact?

Another one: If you had a 13 liter jug and a 5 liter jug, how can you get 9 liters exact?

Also, if these problems are solved before I come back again, what if you can make markings on the jugs? How does the game change?

A E
  • 8,802
  • 5
  • 41
  • 81
the4seasons
  • 564
  • 3
  • 13

2 Answers2

5

All these jug problem variants can be solved by enumerating the entire state space. For the case of a $7$ liter jug and an $11$ liter jug (as mentioned in your post):

  • Every pair $(x,y)$ with integers $x$ and $y$ with $0\le x\le7$ and $0\le y\le11$ forms one state. Draw a corresponding vertex (circle, square) for every state.
  • Every filling and refilling operation translates one state into another state. For every such operation, draw an arc (arrow) from the old state to the new state.
  • The problem has answer YES, if and only if there is a directed path from state $(0,0)$ to state $(0,9)$.

This works well as long as the involved numbers are small (and for larger numbers, use a computer program). Finally, here is a listing with the legal filling and refilling operations:

  • Empty one jug into the barrel: $(x,y) \to (x,0)$ and $(x,y) \to (0,y)$
  • Fill one jug from the barrel: $(x,y) \to (x,11)$ and $(x,y) \to (7,y)$
  • Refill first jug into second: $(x,y) \to (\max\{0,x+y-11\},\,\min\{x+y,11\})$
  • Refill second jug into first: $(x,y) \to (\min\{x+y,7\},\,\max\{0,x+y-7\})$
Gamow
  • 45,573
  • 10
  • 147
  • 381
  • Allowing marks though seems to add a twist to this. Whether you can go from (?, 0) -> (?, 4) would depend on whether you had visited some state (?, 4) previously. Thus the states themselves would need to include the presence of markings, which would increase the state space drastically. – Mark Peters Mar 22 '15 at 15:44
2

For 7 and 11 liters:

Just keep filling the 11 and pouring it into the 7. When the 11 is empty, refill it. When the 7 gets full, empty it. You'll hit 9 eventually. The amount of water in each goes through the following progression (11 liter first):

11, 0; 4, 7; 4, 0; 0, 4; 11, 4; 8, 7; 8, 0; 1, 7; 1, 0; 0, 1; 11, 1; 5, 7; 5, 0; 0, 5; 11, 5; 9, 7

For 13 and 5 liters:

Do the same thing. The amount of water in each goes through the following progression (13 liter first):

13, 0; 8, 5; 8, 0; 3, 5; 3, 0; 0, 3; 13, 3; 11, 5; 6, 5; 6, 0; 1, 5; 1, 0; 0, 1; 13, 1; 9, 5

There may be faster ways, but both of these work. As for allowing marks, I'll have to think about that one.

Duncan
  • 5,045
  • 24
  • 28