Buckets and Jumping Pet
Jaime Rangel-Mondragón · The Mathematica Journal · 2009
Consider the following question. Given two unmarked buckets of capacities 3 and 5 liters, how can we obtain exactly 1 liter of water from an inexhaustible well? The answer is to fill the 3-liter bucket first and empty it into the other bucket. Then, refill the 3-liter bucket from the well and use it to completely fill the other one, leaving the 1 liter desired. This problem is one of a famous category of “decanting” problems that have always appealed to a wide audience, including recreational mathematicians and computer scientists. Similar problems have found valuable applications in the analysis and teaching of algorithmic techniques, typifying many of the difficulties involved in the design of goal-oriented strategies. In the problem of the buckets, it is easy to show that if we have buckets of capacities a and b liters, and we start with both empty, the problem is solvable if and only if a and b are coprime. If this is the case, we have several ways to proceed. Each of them can be described by a sequence of ordered pairs accounting for the states through which we pass at each step towards our goal. Consider for instance, one of the shortest sequences that solves the problem for capacities 2 and 5: {{0, 0}, {0, 5}, {2, 3}, {0, 3}, {2, 1}}.