According to one story [Kasner, p. 159], Siméon Denis Poisson, one of the greatest mathematicians of the 19^th century, owed his interest in mathematics to a chance encounter with a simple problem

In [Ball & Coxeter, p. 27] the problem appears with the remark that "the solution presents no difficulty." It precedes another problem with 4 jugs of capacities 5, 11, 13, and 24 for which a solution "can be worked out only by trial." The problem is presented by the narrative:

More than three years ago I wrote a JavaScript simulation of the 3 Jugs problem. The page since became an all-time favorite with visitors to my site. Here's a more convenient Java variant.

If nothing else, such problems wrap up a meaningful counting exercise that can be handed out to children in early grades.

But there is also some worthwhile mathematics involved that was mostly overlooked by teachers and students alike. (This is judging by the number of questions I received concerning existence of a solution.)

Label the jugs A, B, C in the increasing order of their capacities. Let's agree to use the same letters for the capacities themselves. Let x, y, z denote the quantities of water in the jugs. In particular, x + y + z = C. A typical state - distribution of water - of the puzzle is described by a triple (x, y, z). For the original problem, the initial state is thus (0, 0, C) with C = 8.

Start with (0, 0, C), and pour from C to A and from A to B to obtain (0, A, C - A). This is the basic step that must be repeated until B becomes full: (r, B, C - Aq), for some integers r, q > 0. At this point, pour from B to C and from A to B: (0, r, C - Aq + B) which is just (0, r, 2C - A(q+1)). This a secondary step. Follow with the basic step until B becomes full, after which apply the secondary step, and so on. Modulo C, the third vessel will successively contain the quantities 0, -A, -2A, -3A, ... Since A and B have been assumed mutually prime, so are A and C. Therefore, all quantities 0, -A, -2A, -3A, ..., -A(C-1) are different modulo C. In other words, the set {0, -A (mod C), -2A (mod C), -3A (mod C), ..., -A(C-1) (mod C)} is just a permutation of the set {0, 1, 2, ..., C-1}.

The problem and the proof have a surprising geometric interpretation [Coxeter & Greitzer, p. 89] in terms of triangular coordinates. Cartesian and polar coordinates are great tools of analytic geometry of the plane. Spherical coordinates are suitable for the geometry of the sphere, as are cylindrical coordinates on a cylinder. There are several systems of coordinates in which vertices and sides of a triangle are treated in an equitable manner. The most important are the barycentric and trilinear coordinates.

For example, if r is the inradius - the radius of the inscribed circle - of ABC, then trilinear coordinates of its incenter are (r, r, r) which, in the homogeneous form, appear as r : r : r, or simply as 1:1:1. On the other hand, in the homogeneous barycentric coordinates, 1:1:1 corresponds to the centroid (also called the center of gravity or barycenter) of ABC. For equilateral triangles, the two systems of coordinates coincide.

The description of the 3 Jugs problem as a triple of quantities (x, y, z) fits nicely with trilinear coordinates. Draw an equilateral triangle ABC and let the vertices have trilinear coordinates (C, 0, 0), (0, C, 0), and (0, 0, C) - in that order. The sides AB, BC, and CA are defined by z = 0, x = 0, and y = 0, respectively. The other lines on which one of the coordinates is a constant integer form a triangular grid of lines parallel to the sides of ABC. For example, lines x = const are parallel to the side BC.

The applet below demonstrates how the puzzle moves are reflected on such a grid. (Play with it with the button Trace checked.)

The (integer) points that satisfy built-in constraints of the 3 Jugs problem (e.g., 0xA) fill a parallelogram. Only the points on the boundary of that parallelogram could be attained as a result of valid puzzle moves. The basic move corresponds to an inverted "V" line with one side parallel to AC (pour from C to A), the other to AB (pour from A to B.)

The jug B is full at the points of the "western" side of the parallelogram. Close to that side, the left leg of the inverted V may not reach the bottom line of the parallelogram. In which case, a secondary move must be made: first parallel to the line BC to the "eastern" side of the paralellogram (pour B to C), and then to the bottom side (pour from A to B.)

Since we are only interested in the modular arithmetic, we may overlook the need for secondary moves on the western side of the parallelogram and keep applying only the basic moves. Since A and C are mutually prime, all lines z = const (mod C) will eventually be covered.

Condition A + B = C serves a double purpose. First, together with the relative primality of A and B, it insures that all three capacities share no common factor, save 1. Were they not, the quantities that could be measured with three vessels of the specified capacities would share their common factor. For the problem to be generally solvable the mutual primality of all three capacities is a necessary condition. However, it is not sufficient. Anomalies also arise when the three jugs are rather big. Condition A + B = C prevents this from happening.

This completes the analysis of existence of a solution to the 3 Jugs problem. That of the 2 and 4 Jugs problems is left as an enticement for the future Poissons.

References

1. W.W. Rouse Ball and H.S.M. Coxeter, Mathematical Recreations and Essays, Dover, 1987
2. H.S.M. Coxeter and S.L. Greitzer, Geometry Revisited, MAA 1967
3. E. Kasner and J. Newman, Mathematics and the Imagination, Simon and Schuster, 1958

1. 3 Glasses Problem
2. Puzzle Investigation
3. Application of Graph Theory
4. The puzzle in barycentric coordinates
5. The Three Jugs Problem.
6. Two Pails Puzzle.

Copyright © 2996-2008 Alexander Bogomolny