Theorems to Savor
The Art of Mathematics: Coffee Time in Memphis. Béla Bollobás. xvi + 359 pp. Cambridge University Press, 2006. $85 cloth, $34.99 paper.
The mathematician and puzzle connoisseur Peter Winkler once joked, with a nod to Isaac Newton, "If I have seen farther than others, it is because I have stood on the shoulders of Hungarians." One of these Hungarians is the late Paul Erdös, famous within mathematics for his contributions to number theory and combinatorics and famed more broadly for his unique lifestyle and lingo (children are "epsilons," God is the "Supreme Fascist," God's collection of the best mathematical proofs is "The Book," and so forth). Many of Erdös's collaborators and successors are also Hungarian, and others have adopted what might be called "the Hungarian style," with an emphasis on snappy problems and clever solutions. I can think of no better way to get acquainted with these people and their work than to spend a few months periodically dipping into Béla Bollobás's new collection of mathematical puzzles, titled The Art of Mathematics: Coffee Time in Memphis.
Bollobás (the name is pronounced "bowl o' bosh") is one of the most ardent keepers of the Erdös flame. Since Erdös died—or, as Erdös would say, "left"—in 1996, Bollobás has organized a conference in his honor every year at the University of Memphis. (Full disclosure: I spoke at the 2006 conference.) Bollobás, a professor who divides his time between Trinity College (Cambridge) and the University of Memphis, has worked for decades in functional analysis, combinatorics and graph theory. In the course of years of teaching and research, he has devised (or learned of) many easily stated problems whose solutions possess one or more of the hallmarks that mathematicians prize, such as economy, surprise and fecundity.
Here is one of my favorites: Suppose 10 chairs are arranged in a circle, half of them occupied by students. Show that there exists some whole number n between 1 and 9 such that if each of the 5 students moves n chairs clockwise in the circle, 3 or more of them will end up sitting in a previously occupied chair.
This is not how Bollobás actually poses the problem in his book; in problem 3 (in a series of 157 problems), he asks the reader to consider a more general situation. But the key idea that solves Bollobás's problem can be discovered by thinking about the special case I've described—and by following the clue that Bollobás helpfully provides in a separate section devoted to hints. (If you want to think about this on your own, now would be a good time to put aside this book review!) Bollobás's clue is a short question that at first seems like a non sequitur: "What about a random rotation?"
If we choose n randomly, then each student has a 4-out-of-9 chance of ending up in a previously occupied chair. So on average, the number of students sitting in previously occupied chairs will be 4/9 + 4/9 + 4/9 + 4/9 + 4/9, or 20/9, which is slightly greater than 2. Now comes the punch line: The only way the average value of an integer-valued quantity can exceed 2 is if it sometimes is 3 or greater.
This proof exhibits economy (the chief idea is contained in the five-word hint), surprise (who would think to bring randomness and probability into solving a problem like this?) and fecundity (the probabilistic method has been an enormously powerful tool in the hands of Erdös and others). Bollobás's book is full of tasty little morsels like this one, puzzles whose solution requires attacking them from some unexpected angle. The ability to come up with creative approaches to problems can be cultivated, but it cannot be taught; it is more of an art than a craft. Hence the first half of the book's title.
I prefer Bollobás's original title, Coffee Time in Memphis (which his editor convinced him to lengthen); it bears more of the stamp of Bollobás's personal style. This is a book that developed in the author's mind through the course of conversations with students and colleagues, sometimes in offices or classrooms but just as often in departmental lounges or cafés.
Mathematicians love to find elegant solutions to their research problems, but they can't always be sure that the challenges they set for themselves have sweet answers. It can be a great relief from these uncertainties to work on a problem secure in the knowledge that it has a pleasing solution, which the problem-poser will, if pressed, reveal. Bollobás has included in the book the sorts of problems with which he loves to tease his colleagues and students, with pleasure on both sides.
Fans of books on recreational mathematics should be warned that this one is not for the fainthearted or the mathematically unprepared. For instance, the first sentence of the solution of problem 84 reads, "This assertion is considerably trickier than the usual run-of-the-mill limit questions based on subadditivity or submultiplicativity; here we have to be a little more careful." Bollobás assumes his reader is already acquainted with (and perhaps a bit jaded by) large chunks of the advanced mathematics curriculum. If you do not come equipped with a knowledge of principles like continuity, compactness, contractibility and countability of the rational numbers (to mention just the ones that start with "c"), you will not find all of these problems to be fair challenges; you might want to read this book with a partner and take turns being the one to peek at the sections containing the hints and solutions. On the other hand, some of the puzzles require nothing more than elementary arithmetic and the right perspective on the problem. Some of my own favorites in this latter vein are problems 7, 13, 20, 21, 24, 31, 34, 40, 48, 55, 87, 102 and 119. If you find these more accessible problems fun, you would probably also enjoy Peter Winkler's two collections of brainteasers—Mathematical Puzzles: A Connoisseur's Collection (A K Peters, 2004) and Mathematical Mind-Benders (A K Peters, 2007)—as well as Proofs from THE BOOK, by Martin Aigner and Günter M. Ziegler (3rd ed., Springer, 2004).
Who are the right readers of Bollobás's book? Mathematicians, certainly—especially younger ones who are still building up their mental toolkits. Corporate recruiters in Silicon Valley will probably find some of these problems to be good ways of assessing the mental athleticism of potential hires; in fact, I wouldn't be surprised to learn that some of these puzzles are already being used in this way. On the other side of the interview desk, job seekers might want to practice delivering the solutions to some of the more accessible puzzles, adding some pauses and brief false turns to make the whole thing sound unrehearsed. Likewise, mathematics professors administering oral examinations to Ph.D. students, and Ph.D. students seeking to pass those examinations, might want to go through this book. In addition, students at all levels (high school on up) may find in the notes a source of attractive unsolved research problems.
Erdös's collaborator Paul Turán once remarked that a mathematician is a machine for turning coffee into theorems. If so, then many of the theorems in Bollobás's book represent some extremely potent espresso. It would be a mistake to gulp them down too quickly. If enjoyed at a deliberate rate, alone or in conversation, these problems should have a stimulating effect on the prepared reader who takes the time to savor them.