Don't be fooled by the title of this book. Readers familiar with the New Mathematical Library series, previously published by Random House and now by the MAA, know that it consists of books aimed at excellent high school students, and that those books strive to do difficult and advanced things with elementary mathematics.
The books in the series fall into two broad categories, the problem books, like Hungarian Problem Books I and II (volumes 11 and 12 in the series) or U.S.A. Mathematical Olympiads 1972-1976 (volume 33), and the topical books, The Mathematics of Choice (volume 15), or Elementary Cryptanalysis - A Mathematical Approach (volume 22).
From the title, I had expected this book to fall squarely into the second group, to be a mathematical exposition of the wonders of iteration. I was wrong. Over and Over Againdoes not fall neatly into either category, though it is more of a problem book than a topical one.
Over and Over Again explains the mathematics behind many of the problems that appear in the high school mathematics contests, particularly the International Math Olympiads (IMOs) and their national counterparts in China and the United States. Many, but not all, of the problems involve iteration, but the real focus of the book is contest problem solving and how it is related to the underlying mathematics. It starts to dispel the "bag of tricks" air that clings to contest problem solving, and to replace it with a more systematic "box of tools."
One of the first problems in the first chapter is to show why iterating the function f(x)=(x + a/x)/2 converges so rapidly to the square root of a (if a and x are both positive). These were the kinds of iterative applications that I expected to dominate the book.
The second chapter, though, was about using the Arithmetic-Geometric Mean theorem to solve max-min problems. That didn't seem very iterative, until nearly the last paragraph of the chapter, where it suddenly had an application to one of the problems in Gauss diary.
The very short chapter six is based on an apparently simple problem. A number of student are sitting in a circle, and each student has an even number of pieces of candy. On a signal, each student passes half of his or her trove to the student on his or her right. Between signals, the teacher gives any student with an odd number of candies one more piece to make the number even, and the signal is given again. The problem is to show that, after a finite number of iterations, all the students have the same number of pieces of candy.
A good way to solve the problem is to devise an integer valued measure of the inequity of the distribution, such that the measure equals zero exactly when all the students have the same number of pieces, and then to show that whenever the measure is non-zero, the iteration must decrease the measure. Once you have the plan, the only trick is to devise such a measure, and our authors provide us with several of them. The authors tell us that such processes are called "smoothing processes."
Ten chapters later, smoothing processes are still going strong. Form a general n-gon in the plane by connecting n vertices in any order and allowing edges to intersect. Transform this n-gon into a new one by connecting the midpoint of each edge to the midpoints of the two edges adjacent to it. Iterating this transformation tends to make the n-gon a little smaller, but it also makes the vertices of the n-gon tend to become vertices on an ellipse. Try it yourself on Matlab or something. It is surprising how quickly even twisted and convoluted n-gons smooth out and become very ellipse-like.
That turns out to be related to Sharkovskii's theorem, that period 3 implies chaos, to splines and Bezier curves, to Napoleon's theorem and, apparently, to everything else in the world.
As with most books in the series, Over and Over Again tries to use only "high school" mathematics. For these authors, that means that they try to avoid calculus until the last third of the book. For most of us, their definition of "high school" mathematics is a bit optimistic, including, as it does, such topics as cross ratios from complex numbers and eigenvalues from linear algebra.
This is a fine book for learning how people find and develop the problems they inflict on Math Olympiad participants. It also reveals contest problem solving as a learnable skill, distinct from other things called problem solving, and, perhaps also distinct from that thing we call "mathematics." It also contains some interesting and entertaining mathematics.
Finally, the double nature of this book as a problem book and a topical book is apparent. There is the obvious topic, iteration, but there is also the key to learning to solve problems, and that is to do them over and over again.
Ed Sandifer (firstname.lastname@example.org) is a professor of mathematics at Western Connecticut State University and has run the Boston Marathon 25 times.