The Art and Craft of Problem Solving

9.2.20 Draw two nonintersecting circles on a piece of
paper. Show that it is possible to draw a straight line
that divides each circle into equal halves. That was
easy. Next,
(a) What if the two shapes were arbitrary noninter­
secting rectangles, instead of circles?
(b) What if the two shapes were arbitrary noninter­
secting convex polygons, instead of circles?
(c) What if the two shapes were arbitrary noninter­
secting "amoebas," possibly not convex?

9.2.21 (Putnam 1995) Evaluate

8 2207 _
I
2207 -
2 20L
Express your answer in the form (a + by'C) / d, where
a,b,c,d are integers.
9.2.22 Here is an allegory that should provide you
with a strategy (the "repeated bisection method") for a
rigorous proof of the intermediate value theorem. Con­
sider the concrete problem of trying to find the square
of 2 with a calculator that doesn't have a square-root
key. Since 12 = I and 22 = 4, we figure that v'2, if
it exists, is between I and 2. So now we guess 1 .5.
But 1.5^2 > 2, so our mystery number lies between I
and 1.5. We try 1.25. This proves to be too small, so
next we try �(1. 25 + 1 .5), etc. We thus construct a se­
quence of successive approximations, alternating be­
tween too big and too small, but each approximation
gets better and better.
9.2.23 (Leningrad Mathematical Olympiad 1991) Let
1 be continuous and monotonically increasing, with
1(0) = 0 and I( I) = 1. Prove that

1

(/ 0 )

+1

( 1

2

0 )

+

... +/(�o)

+

rl (/ 0 ) +rl C

2

0 )

+···+rl

(�o) � ��.

9.2.24 (Leningrad Mathematical Olympiad 1988) Let
I: JR -+ JR be continuous, with I(x)· l(f(x)) = I for
all x E JR. If I( 1000) = 999, find 1(500).

9.2.25 Let 1 : [0, I] -+ JR be continuous, and sup­
pose that 1(0) = 1(1). Show that there is a value
x E [0, 199 8 /1999] satisfying I(x) = I(x+ 1/1999).

9.2.26 Show that v'n+T -Vri = O( Vri).

9.2.27 Fill in the details for Example 9.2.3.

9.2 CONVERGENCE AND CONTINUITY 327

9.2.28 Use Problem 9.2.17 to get a different solution

to 9.2.3, by showing that the set

{V'n-Vm: n,m = 0, 1,2, ... }

is dense.

9.2.29 (Putnam 1992) For any pair (x,y) of real num­

bers, a sequence (an (x,y)k:::o is defined as follows:

ao(x,y) =x,

( )

(an(X,y))^2 +l

an+1 x,y =

2

Find the area of the region

for n � o.

{(x,y)l(an(x,y)k?:o converges}.

9.2.30 Let (xn) be a sequence satisfying

nlim --->OO (xn -Xn-I) = O.

Prove that

lim

Xn

n-+OO = O.

n

9.2.3 1 (Putnam 1970) Given a sequence (xn) such that

nlim --->oo (xn -Xn-^2 ) = O. Prove that

lim

Xn -Xn-I

n---"oo = O.

n

Infinite Series of Constant Terms

If (an) is a sequence of real numbers, we define the in-

00

finite series � ak to be the limit, if it exists, of the se­

k= 1

n

quence of partial sums (sn), wheresn := � ak. Prob-

k=1

lems 9.2.32-9.2.38 below play around with infinite se-

ries of constant terms. (You may want to reread the

section on infinite series in Chapter 5, and in particu­

lar Example 5.3.4 on page 161.)

9.2.32 Show rigorously that if Irl < I, then

a+ar+ar^2 +ar^3 + ... = _

a

_.

l - r

00

9.2.33 Let � ak be a convergent infinite series, i.e.,

k=1

the partial sums converge. Prove that

(a) nlim --->oo an = 0;