Mathematics for Computer Science

Chapter 8 Number Theory188

theb-jug is big enough:

.0;0/!.a;0/ fill first jug

!.0;a/ pour first into second

!.a;a/ fill first jug

!.2ab;b/ pour first into second (assuming2ab)

!.2ab;0/ empty second jug

!.0;2ab/ pour first into second

!.a;2ab/ fill first

!.3a2b;b/ pour first into second (assuming3a2b)

What leaps out is that at every step, the amount of water in each jug is of a linear
combination ofaandb. This is easy to prove by induction on the number of
transitions:

Lemma 8.1.6(Water Jugs).In theDie Hardstate machine of Section 6.2.4 with
jugs of sizesaandb, the amount of water in each jug is always a linear combination
ofaandb.

Proof. The induction hypothesis,P.n/, is the proposition that afterntransitions,
the amount of water in each jug is a linear combination ofaandb.

Base case(nD 0 ):P.0/is true, because both jugs are initially empty, and 0
aC
0
bD 0.

Inductive step: Suppose the machine is in state.x;y/afternsteps, that is, the little
jug containsxgallons and the big one containsygallons. There are two cases:

 If we fill a jug from the fountain or empty a jug into the fountain, then that jug

is empty or full. The amount in the other jug remains a linear combination

ofaandb. SoP.nC1/holds.

 Otherwise, we pour water from one jug to another until one is empty or the

other is full. By our assumption, the amountxandyin each jug is a linear

combination ofaandbbefore we begin pouring. After pouring, one jug is

either empty (contains 0 gallons) or full (containsaorbgallons). Thus, the

other jug contains eitherxCygallons,xCya, orxCybgallons, all

of which are linear combinations ofaandbsincexandyare. SoP.nC1/

holds in this case as well.

SinceP.nC1/holds in any case, this proves the inductive step, completing the
proof by induction.