The Art and Craft of Problem Solving

80 CHAPTER 3 TACTICS FOR SOLVING PROBLEMS

Solution: There are several things to which we can apply extreme arguments.

Since f(x) 20 , we might want to look at the value of x at which f(x) is minimal. First

we need to prove that this value actually exists, i.e., that there is an Xo E lR such that

f(xo) is minimal. [This is not true for all functions, such as f(x) = l/x.] Write

f(x) = anx" +an_ 1 x"-1 + ... +alx+aO,

where each ai E lR. Since f(x) is always non-negative, the leading coefficient an must

be positive, since the leading term an� dominates the value of f(x) when x is a large

positive or negative number. Moreover, we know that n is even. So we know that

lim f(x) = lim f(x) = +00,

x---+-oo x---++oo

and consequently, f(x) has a minimum value. Notice that g(x) has the same leading

term as f(x) so g(x) also has a minimum value. Indeed, g(x) is what we will focus

our attention on. We wish to show that this polynomial is always non-negative, so

a promising strategy is contradiction. Assume that g(x) < 0 for some values of x.

Consider its minimum value, achieved when x = Xo. Then g(xo) < O. Now, what is the

relationship between g(x) and f(x)? Since f(x) is nth degree, r+^1 (x) = 0 and

g'(x) = J'(x) + f"(x) + ... + f(n) (x) = g(x) - f(x).

Consequently,

g'(xo) = g(xo) - f(xo) < 0,

since g(xo) is strictly negative and f(xo) is non-negative by hypothesis. But this con­

tradicts the fact that g(x) achieves its minimum value atxo, for then g'(xo) should equal

zero! _

In the next example, Gaussian pairing plus monotonization help solve a rather

difficult problem, from the 1994 IMO in Hong Kong.

Example 3.2.6 Let m and n be positive integers. Let al ,a2, ... ,am be distinct elements

of {I, 2, ... ,n} such that whenever ai + a j � n for some i, j, 1 � i � j � m, there exists

k, 1 � k � m, with ai +aj = ak. Prove that

al + a2 + ... + am n + I

m 2 - 2

- ·

Solution: This is not an easy problem. Part of the difficulty is figuring out the

statement of the problem! Let us call those sequences that have the property described

in the problem "good" sequences. In other words, a good sequence is a sequence

ai, a2, ... ,am of distinct elements of {I, 2, ... ,n} such that whenever ai + a j � n for

some i, j, 1 � i � j � m, there exists k, 1 � k � m, with ai +a j = ak. Begin by plugging

in easy values for m and n, say m = 4 ,n = 100. We have the sequence al,a2,a3,a4 of

distinct positive integers that may range between 1 and 100, inclusive. One possible

such sequence is 5 , 93 ,14, 99. Is this a good sequence? Note that al + a2 = 98 � 100,

so we need there to be a k such that ak = 98. Alas, there is not. Improving the original

sequence, we try 5 , 93 ,98, 99. Now check for pairs that add up to 100 or less. There