3.4 Problem 4: The 3-jug Problem

This is another example for using the concept of graph to model the problem. The problem can be formulated as a number of states and transitions between the states. A state is a particular filling of the jugs, for instance, a state is: “the 8-liter jug contains 8 liters of water, the 5-liter jug contains nothing, and the 3-liter jug contains nothing.” Each state can be represented by a triple of numbers: (x,y,z), where x is the content of the 8-liter jug, y is the content of the 5-liter jug, and z is the content of the 3-liter jug. So, (8, 0, 0) is the example just used before. We want to reach the state (4, 4, 0). The capacities of the jug can also be represented by a triple: (8, 5, 3).

The first step is to enumerated all states. There are 216 potential states, namely, all states (x,y,z) with 0 x 8, 0 y 5, and 0 z 3, which is 9 6 4 = 216. However, only states with the condition x + y + z = 8 are allowed (no water should be added or removed). Furthermore, at least one jug must be full or empty – following the rules of pouring. This condition can be represented as a Boolean expression. x = 0 x = 8 y = 0 y = 5 z = 0 z = 3. There are 16 remaining possible states, they are:

{(0,5,3),(1,4,3),(1,5,2),(2,3,3 ),(2,5, 1),(3, 2,3),(3,5,0),(4,1,3),
     (4,4,0 ),(5,0, 3),(5, 3,0),(6,0,2),(6,2,0),(7,0,1),(7,1,0),(8,0,0)}

The basic operation is to pour water from one jug A to another jug B in a way that either A is emptied or B is filled. We are looking for the shortest sequence of operations that reaches the state (4, 4, 0) starting with state (8, 0, 0). Such a basic operation is called a transition from one state to another. You noticed? The “problem of the 3-jugs” has been transformed into a “problem of states and transitions between the states”. The final step is to position the states somewhere in the plane and link two states with an arrow, if a transition from the first to the second state is possible. The result is a (directed) graph, a graph with directed links. The problem now is reduced to find the shortest (direct) path in this graph from state (8, 0, 0) to the state (4, 4, 0). The resulting graph and the shortest path in red is given in Figure 4.

I guess it is clear how to interpret the solution: In the first step, take the 8-liter jug and fill the 5-liter jug, the second step is to take the 5-liter jug and to fill the 3-liter jug, the thrid step is to empty the 3-liter jug and pour it to the 8-liter jug, and so on, 7 steps are needed to get to the goal (4, 40).


PIC

Figure 4: Solution of the 3-Jug Problem

Interestingly, we not only know now how to solve this particular 3-jug problem but all kind of jug problems with other capacities and with a different number of jugs. This is a strong indication of a good model: if the model’s vocabulary stimulates others undiscovered aspects of the problem or guides the research to similar problems, then the model might be reasonably good. If, however, the vocabulary is “sticky” or “artificial” then the model is probably not very useful.