(Two containers and a pond are depicted in the right-hand side of the applet. To pour water, first click on the "source" and then on the "receiver" object.
This puzzle is no different from the 3 Jugs Problem. Indeed, the problem with two containers of capacities 11 and 6 is the same as the problem with 3 containers of capacities 11, 6, and 17 ( = 11 + 6). Which shows that, to solve our original problem all we need is 17 gallons of water. Of course having a pond - thought of as an unlimited source and also as a bottomless receiver of water - is a convenience in practical terms, but is irrelevant to solving the puzzle.
From the analysis of the 3 Jugs Problem, we already know that the more general problem with integer capacities A and B always has a solution iff A and B are mutually prime.
However the argument there made a heavy use of the third quantity C - capacity of the third container. This is not necessary as we may directly work in Cartesian coordinates, instead of the barycentrics. Let A > B be mutually prime. As the basic step we consider pouring from the pond to B and from B to A. Sooner or later, A will become full, at which stage we apply the secondary step by emptying A into the pond and pouring the content of B into A. The secondary step is applied only when A becomes full. If A = qB + r, then the first time this happens container B will be left with (B - r) units of water. Completing the basic step followed by one secondary step, we get (B - r) gallons in the first container with the second one empty. In coordinates: (B - r, 0). It's a great convenience to consider each coordinate modulo A. Using arithmetic modulo A, we conclude that every sequence of basic steps that fills up the first container, followed by one secondary step, changes the pair (x, 0) by a vector (B - r, 0). Several such sequences will produce pairs (B - r, 0), (2(B - r), 0), (3(B - r), 0), and so on. Since B - r = (q + 1)B - A, and B and A are assumed to be mutually prime, so are A and B - r, and the sequence of the first coordinates becomes
(B - r) (mod A), 2(B - r) (mod A), 3(B-r) (mod A), ...
which, as we know, fills the entire set {0, 1, 2, ..., A-1}.
In addition, once a quantity from the set {0, 1, 2, ..., A-1} is secured in container A, we may fill container B to deliver any quantity of water that does not exceed A + B. (A + B is obtained in a trivial manner by just fillng both containers.)
- 3 Glasses Problem
- Puzzle Investigation
- Application of Graph Theory
- The puzzle in barycentric coordinates
- Three Jugs Problem.
- Two Pails Puzzle.
Copyright © 1996-2008 Alexander Bogomolny
