Three And Five Liters

There is this classic riddle where you are given two containers, one has a capacity of three liters and the other five liters. Your task is to extract exactly four liters. There are no further markings on the containers.

To measure two liters, it is quite straightforward: Fill the five liter container, transfer to the three liter container until the latter is full. Then there will be two liters remaining in the five liter container. To obtain one or four liters takes more steps. I wondered what results are possible with this setup. Can you achieve any amount of liquid in both of the containers?

Matrices and vectors

This problem can be expressed with simple matrices and vectors. First we have to choose a basis for this problem. The following is just the outer product of the possible fill levels for two containers, now labeled with C3 and C5:

There are 24 basis states as the first container has four states (0, 1, 2, and 3 liters) and the second one has six states (0, 1, 2, 3, 4, and 5 liters). There are the following operations:

F3

Fill C3

F5

Fill C5

D3

Dump the contents of C3

D5

Dump the contents of C5

T35

Transfer liquid from C3 into C5 until C5 is full or C3 is empty

T53

Transfer from C5 to C3

We already know that there are at most 24 different states that our system of two containers can be in. We start with both containers empty. Now we can apply each operation to this state and see which state we then obtain. We repeat that with each operator on each intermediate result until we do not get a state that was not encountered before. Due to the finite nature of the elements we are sure that eventually this algorithm will terminate.

In the little program all possible states are constructed. Here are the possible resulting states of the systems as well as the operations needed to obtain from the empty state:

One can see that we can create any sum between 0 and 8. Some end states might be obtainable via multiple ways.

Graph viewpoint

An alternative view onto this problem is via graph theory. The operators expressed as matrices can be interpreted as adjacency relations. We want to know which vertices (states of the system) can be reached from the start vertex.

The start vertex is marked in yellow, reachable vertices in orange. Vertices without filling cannot be reached by any of the operations available.

In order to find the connected part of the graph we express an operator like T53 as this matrix:

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

In order to get the whole connections between the vertices, we just sum all the matrix representations of the operators. Values greater than 1 are just set to 1 as we are interested in the connectivity only. The result is the following adjacency matrix:

1 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0
0 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0
0 0 1 0 0 1 1 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0
1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 1 0 0 0 1 0 0 0 1
0 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 1 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0
0 0 1 0 0 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 1 0 0 1 0 0 0
0 0 0 1 0 0 1 0 0 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 1 0 0
0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 0
1 0 0 0 1 0 0 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1
0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1 1 0 0 1 0 0
0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 1 0
0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 1 1 1

Using a proper graph library like igraph, one can further investigate this graph. We convert the adjacency matrix into a graph with g <- graph_from_adjacency_matrix(adj_matrix). Then using all_simple_paths(g, 1, 4) we can obtain all paths that start at vertex 1 (the all empty state) and go to state 4, which is [3, 0]. By looping over the final vertex we can find out if there is at least one path to the desired state. The list of reachable states turns out to be exactly the same as before.

Looking at the shortest possible path for each of the states, I found that in order to reach state 7, the [3, 1] one, only seven operations are needed, not eight. My naive algorithm has given me this:

F5 T53 D3 T53 F5 T53 D3 T53

The graph library however has found this shorter path:

F3 T35 F3 T35 D5 T35 F3

Conclusion

This simple riddle has a rather intricate structure to it, using vectors and matrices we were able to find all possible results. Using graph theory an even more elegant formulation is found, which allows retrieval of the shortest paths between any two states of the system.