Chapter 8 Number Theory194
At the end of this process, we must have 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 that approach gives:
.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
the amount we’re trying to produce! Simply repeat these two steps until the desired
amount of water is obtained:
- Fill the smaller jug.