Barycentric coordinates, three jugs application

Barycentric coordinates
A Curious Application

We are given three glasses A, B, C of respective capacities 8, 5, and 3 oz. The first glass is full of water. The problem is to measure out 4 oz of water (without, of course, spilling a single drop.)

With the points A, B, C we associate barycentric coordinates u, v, w such that

u + v + w = 8

The grid on the right represents points with all three coordinates non-negative integers. Strings correspond to the coordinate values. For example, the apex A is referred to by its coordinate string 800 which is just a shorthand for u = 8, v = 0, w = 0 or (8, 0, 0). To account for limited capacities of the given vessels, note that under no circumstances it is possible to arrive at the water distribution represented by, say, 134. For the third glass is only capable of holding 3 oz of water. The region of feasible configurations is bounded by the red parallelogram.

Pouring from one glass to another corresponds to moving from one node to another along one of the grid lines (on which the quantity of water in the remaining glass does not change!) Since the only way to measure an exact quantity is by either completely filling or completely emptying one of the glasses, we always move up to the boundary of the red parallelogram. Consider, for example, point 431 - the blue dot on the diagram. From here there are 6 possible moves (in the counterclockwise direction:

to 701 (pour 3 oz from #2 to #1)
to 530 (pour 1 oz from #3 to #1)
to 440 (pour 1 oz from #3 to #2)
to 251 (pour 2 oz from #1 to #2)
to 233 (pour 2 oz from #1 to #3)
to 413 (pour 2 oz from #2 to #3)

Since, at the beginning, the first glass is full, we start at the vertex 800. From there there are only two moves: along the side w = 0 to the node 350 or along the side v = 0 to the node 503. Solving the problem is like playing billiard on a triangle table (We already used a rectangular table for the same purpose.) There are just three nodes on the red parallelogram that contain at least one 4: 440, 413, 143. The problem will be solved when the ball arrives at one of these points.

The situation is not always as simple as that. For example, assume we are given glasses of capacities 8,7, and 6 that, between them, hold 10 oz of water. For one, the set of feasible nodes is now bounded by an irregular hexagon, not a parallelogram. Secondly, not all configurations are reachable from all starting positions. For example, nodes 550-505-055 form a loop so that unless the initial node lies on one of the lines connecting the three nodes, it is impossible to get there. Which means that it is impossible to measure out 5 oz unless one of the glasses held 5 oz to start with.

Other anomalies arise when the given capacities have a common factor greater than 1. In this case too, the set of boundary nodes (of the feasible hexagon) is split into nonintersecting loops. A problem is only solvable if both its starting and goal configurations belong to the same loop.

References

H. S. M. Coxeter, Introduction to Geometry, John Wiley & Sons, 1961

71861535