8.2. The Greatest Common Divisor 253
- Pour all the water in the 21-gallon jug into the 26-gallon jug. If at any time
the 26-gallon jug becomes full, empty it out, and continue pouring the 21-
gallon jug into the 26-gallon jug.
At the end of this process, we must have emptied the 26-gallon jug exactly t^0
times. Here’s why: we’ve takens^0 21 gallons of water from the fountain, and
we’ve poured out some multiple of 26 gallons. If we emptied fewer than t^0 times,
then by (8.6), the big jug would be left with at least 3 C 26 gallons, which is more
than it can hold; if we emptied it more times, the big jug would be left containing
at most 3 26 gallons, which is nonsense. But once we have emptied the 26-gallon
jug exactly t^0 times, equation (8.6) implies that there are exactly 3 gallons left.
Remarkably, we don’t even need to know the coefficientss^0 andt^0 in order to
use this strategy! Instead of repeating the outer loops^0 times, we could just repeat
until we obtain 3 gallons, since that must happen eventually. Of course, we have to
keep track of the amounts in the two jugs so we know when we’re done. Here’s the
solution using this approach starting with empty jugs, that is, at.0;0/:
fill 21
! .21;0/pour 21 into 26
! .0;21/
fill 21
! .21;21/pour 21 to 26
! .16;26/empty 26
! .16;0/pour 21 to 26
! .0;16/
fill 21
! .21;16/pour 21 to 26
! .11;26/empty 26
! .11;0/pour 21 to 26
! .0;11/
fill 21
! .21;11/pour 21 to 26
! .6;26/empty 26
! .6;0/pour 21 to 26
! .0;6/
fill 21
! .21;6/pour 21 to 26
! .1;26/empty 26
! .1;0/pour 21 to 26
! .0;1/
fill 21
! .21;1/pour 21 to 26
! .0;22/
fill 21
! .21;22/pour 21 to 26
! .17;26/empty 26
! .17;0/pour 21 to 26
! .0;17/
fill 21
! .21;17/pour 21 to 26
! .12;26/empty 26
! .12;0/pour 21 to 26
! .0;12/
fill 21
! .21;12/pour 21 to 26
! .7;26/empty 26
! .7;0/pour 21 to 26
! .0;7/
fill 21
! .21;7/pour 21 to 26
! .2;26/empty 26
! .2;0/pour 21 to 26
! .0;2/
fill 21
! .21;2/pour 21 to 26
! .0;23/
fill 21
! .21;23/pour 21 to 26
! .18;26/empty 26
! .18;0/pour 21 to 26
! .0;18/
fill 21
! .21;18/pour 21 to 26
! .13;26/empty 26
! .13;0/pour 21 to 26
! .0;13/
fill 21
! .21;13/pour 21 to 26
! .8;26/empty 26
! .8;0/pour 21 to 26
! .0;8/
fill 21
! .21;8/pour 21 to 26
! .3;26/empty 26
! .3;0/pour 21 to 26
! .0;3/
The same approach works regardless of the jug capacities and even regardless of
the amount we’re trying to produce! Simply repeat these two steps until the desired
amount of water is obtained: