The Art and Craft of Problem Solving

partner.

3.2 THE EXTREME PRINCIPLE 77

Now, let us remove X and Y from the party. If we no longer count handshakes
involving these two people, we are reduced to a party with n invited couples, and ev­
eryone's handshake number (other than the host, about whom we have no information)
has dropped by exactly 1, since everyone shook hands with X and no one shook hands

with Y. But the inductive hypothesis P( n) tells us that the hostess at this "abridged"

party shook n hands. But in reality, the hostess shook one more hand-that of the X

whom we just removed. So in the party with n + 1 invited guests, the hostess shook

n + 1 hands, establishing P( n + 1). •

Often, problems involve the extreme principle plus a particular argument style,
such as contradiction or induction. A common tactic is to use the extremes to "strip
down" a problem into a smaller version, as above. The formal argument then uses
induction. Here is another example. As above, we break down our solution into an
informal investigation, followed by a formal write-up.

Example 3.2.4 (St. Petersburg City Olympiad 1996) Several positive integers are writ­

ten on a blackboard. One can erase any two distinct integers and write their greatest
common divisor and least common multiple instead. Prove that eventually the numbers
will stop changing.

Investigation: Before we begin, we mention a few simple number theory defini­

tions. See Chapter 7 for more details.

• For integers a and b, the notation alb means "a divides b"; i.e., there exists an
  integer m such that am = b.


• The greatest common divisor of a and b is defined to be the largest integer g
  satisfying both gla and glb. The notation used is GCD(a, b). Sometimes (a,b)
  is also used.

• The least common multiple of a and b is defined to be the smallest positive

integer u satisfying both alu and blu. The notation used is LCM(a,b). Some­

times [a , b] is also used. We have to specify that the least common multiple is

positive, otherwise it would be -oo!

Start with a simple example of two numbers such as 10 , 15. This is immediately

transformed into 5, 30, which thereafter never changes, since 5130. Here is a more

complicated example. We will write in boldface the two elements that get erased and
replaced,

11

11

1

1

16 30

2 240

2 240

2 24

72

72

792

7920,

and once again, the sequence will not change after this, since

11 2, 2 124 , 2417920.

A few more experiments (do them!) lead easily to the following conjecture: