Question

There are three containers whose size are 3 pints, 5 pints, and 7 pints, respectively. The 3-pint and 5-pint containers start out full of water, but the 7-pint container is initially empty. We are allowed one type of operation: pouring the contents of one container into another, stopping only when the source container is empty or the destination container is full. We want to know if there is a sequence of pourings that leaves exactly 6 pints in the 7-pint container. (a) Model this as a graph problem: give a precise definition of the graph involved and state the specific question about this graph that needs to be answered. (b) What algorithm should be applied to solve the problem? (c) Find the answer by applying the algorithm.

Answer 1

Here is one of the way to solve this problem (check the states transitions) (3/3, 5/5, 0/7) rightarrow (0/3, 5/5, 3/7) rightarrow (3/3, 2/5, 3/7) rightarrow (0/3, 2/5, 6/7) (a) to make a graphical model, we will represent each potential state of the three - containers with an ordered pair (p, q) , where p is amount in 3 - point container and q - is a moment in 5 - points container, note that we don't heel, 3 variable states as amount in 3 -point and 5 point container is sufficient to describe the state of the 7 - bits container as well, since total water is fixed at 8 liters . possible states = (3 + 1) times (5 + 1) = 24, we have added '1' for the empty state of container we will follow path starting from state (3, 5) to (0, 2) \r\n (b) given above constant method graph, we start at note (3, 5)