The Art and Craft of Problem Solving

78 CHAPTER^3 TACTICS FOR SOLVING PROBLEMS

Eventually, the sequence will fo rm a chain where each element will di­

vide the next (when arranged in order). Moreover, the least element and

the greatest element of this chain are respectively the greatest common

divisor and least common multiple of all the original numhers.

How do we use the extreme principle to prove this? Focus on the least ele­

ment of the sequence at each stage. In the example above, the least elements were

11 , (^2) , 1 , 1. Likewise, look at the greatest elements. In our example, these elements were
(^72) , (^240) ,792, 7290. We observe that the sequence of least elements is non-increasing,

while the sequence of greatest elements is non-decreasing. Why is this true? Let a < h

be two elements that get erased and replaced by

GCD(a, h), LCM(a, h).

Notice that if alh, then a = GCD(a,b) and h = LCM(a, h), so the sequence is un­

changed. Otherwise we have GCD( a, h) < a and LCM( a, h) > h. Consequently, if x is

the current least element, on the next turn, either

• We erase x and another element y (of course we assume that x does not divide

y), replacing x with GCD(x,y) < x, producing a new, smaller least element.

• We erase two elements, neither of which was equal to x. In this case, the smaller

of the two new elements created is either smaller than x, producing a new least

element, or greater than or equal to x, in which case x is still the least element.

A completely analogous argument works for the greatest element, but for now,

let's just concentrate on the least element. We know that the least element either stays

the same or decreases each time we erase-and-replace. Eventually, it will hit rock

bottom. Why? The maximum possible value that we can ever encounter is the least

common multiple of the original elements, so there are only finitely many possible

values for our sequence at each stage. Either eventually the sequence cannot change,

in which case we're done-this is what what we wanted to prove--or eventually the

sequence will repeat. Thus we can distinguish a smallest least element, i.e., the small­

est possible least element f that ever occurs as our sequence evolves. We claim that f

must divide all other elements in the sequence in which it appears. For if not, then we

would have fIx for some element x, and then if we erase-and-replace the pair C,x, the

replaced element GCD(f,x) < f, contradicting the minimality of f.

Why is this good? Because once the minimal element f is attained, it can be

ignored, since f divides all the other elements and hence the sequence will not change

if we try to erase-and-replace two elements, one of which is f. Hence the "active" part

of the sequence has been shortened by one element.

This is just enough leverage to push through an induction proof! Let us conclude

with a formal argument.

Formal Solution: We will prove the assertion by induction on the number of

elements n in the sequence. The base case for n = 2 is obvious: a, h becomes

GCD(a, h), LCM(a, h)

which then no longer changes.