Three Glass Puzzle

Graph Theoretical Approach

Oystein Ore gave a worldly twist to the Three Glass puzzle and solved it in the framework of the Graph Theory.

There are three jugs A, B, C, with capacities 8,5,3 quarts, respectively. The jug A is filled with wine, and we wish to divide the wine into two equal parts by pouring it from one container to another - that is, without using any measuring devices other than these jugs.

Every distribution of wine in the three jugs A, B, and C, can be described by the quantities b and c of wine in the jugs B and C, respectively. Thus every possible distribution of wine is described by a pair (b, c). Initially b=c=0 so that one starts with the distribution (0, 0). The target distribution is obviously (4, 0).

puz(WaterPuzzle) in this case consists of all integer pairs (b,c) connected by edges wherever it's possible to move from one node to another by pouring wine between the jugs. Thus, from (0, 0) we can move to (5, 0) and (0, 3). From (5, 0) it's possible to move back to (0, 0) but also to (2, 3) by pouring from B to C and to (5, 3) by pouring from A to C. Continuing in this manner we'll discover that the nodes of the graph corresponding to the feasible configurations of wine are located on the perimeter of the 6x4 rectangle in the first quadrant. (Why?)

On the diagram I only showed some of the edges. In particular, there is a walk from the starting node (0, 0) to the target node (4, 0), viz.

(0,0)	(A->B)
(5,0)	(B->C)
(2,3)	(C->A)
(2,0)	(B->C)
(0,2)	(A->B)
(5,2)	(B->C)
(4,3)	(C->A)
(4,0)

Complete puz(WaterPuzzle), as it follows from the proof of one of the statements derived previously, consists of all possible horizontal, vertical, and diagonal (upper-left-to-bottom-right) edges that connect perimeter points.

Remark

It's perhaps relevant to note that puz(WaterPuzzle) with nodes on the perimeter of the 6×4 rectangle resembles the diagram obtained in describing a slanted cut of the torus with a rational slope. In this case the cut here proceeds in the mirror direction of that on the torus. As I just noted all the diagonal lines connecting points on the perimeter are included. This shows that the serpentine band is indeed of constant width.

Reference

O. Ore (R. J. Wilson), Graphs And Their Uses, MAA, New Math Library, 1990.

40611754