The Art and Craft of Problem Solving

(b) Between any two irrational numbers there is a

rational number.

5.1.5 The number of elements of a set is called its

cardinality. The cardinality of A is usually indicated

by IAI or #A. If IA I = m and IBI = n, then certainly

IA x BI = mn. How many different functions are there

from A toB?

5.1. 6 (AIME 1984) The function f : Z --+ Z satisfies

f(n) = n -3 if n � 1000 and f(n) = f(f(n + 5)) if

n < 1000. Find f(84).

5.1.7 (AIME 1984) A function f is defined for all real

numbers and satisfies

f(2+x) = f(2 -x) and f(7 +x) = f(7 -x)

for all real x. If x = 0 is a root of f(x) = 0, what is

the least number of roots f(x) = 0 must have in the

interval -1000 :$ x :$ 1000?

5.1.8 (AIME 1985) How many of the first 1000 posi·

5.2 Algebraic Manipulation Revisited

5.2 ALGEBRAIC MANIPULATION REVISITED 147

tive integers can be expressed in the form

l2xJ + l4xJ + l6xJ + l8xJ?

5.1. 9 True or false and why: l JfxJJ = l v'xJ for all

non·negative x.

5.1.10 Prove that for all n E N,

5.1.11 Try Problem 2.4.19 on page 60.

5.1.12 Find a formula for the nth term of the sequence

1,2,2,3,3 , 3,4,4,4,4,5,5,5,5,5, ...

where the integer m occurs exactly m times.

5.1.13 Prove that

l

n

;,

20

J + l

n

;t J + l

n

;t J + ... + l

n +

2

:

n-'

J =n

for any positive integer n.

Algebra is commonly taught as a series of computational techniques. We say "compu­

tational" because there really is no conceptual difference between these two exercises:

l. Compute 42 x 5 7.

2. Write (4x + 2) (5x + 7) as a trinomial.
   Both are exercises of routine, boring algorithms. The first manipulates pure numbers
   while the second manipulates both numbers and symbols. We call such mind-numbing
   (albeit useful) algorithms "computations." Algebra is full of these algorithms, and you
   have undoubtedly practiced many of them. What you may not have learned, however,
   is that algebra is also an aesthetic subject. Sometimes one has to slog through messy
   thickets of algebraic expressions to solve a problem. But these unfortunate occasions
   are pretty rare. A good problem solver takes a more confident approach to algebraic
   problems. The wishful thinking strategy teaches her to look for an elegant solution.
   Cultivate this mind set: employ a light, almost delicate touch, keeping watch for oppor­
   tunities that avoid ugly manipulations in favor of elegant, often symmetrical patterns.
   Our first example illustrates this.
   Example 5.2.1 If x + y = xy = 3, find x^3 + y^3.
   Solution: One way to do this problem-the bad way-is to solve the system
   xy = 3,x + y = 3 for x and y (this would use the quadratic formula, and the solutions
   will be complex numbers) and then substitute these values into the expression x^3 + y^3.
   This will work, but it is ugly and tedious and messy and surely error-prone.
   Instead, we keep a light touch. Our goal is x^3 + y^3 , so let's try for x^2 + i as a
   penultimate step. How to get x^2 + i? Try by squaring x+ y.