by Jonathan Kujawa
In 1894 Benjamin Finkel, a teacher at the Kidder Institute in Missouri, founded the American Mathematical Monthly. Its purpose was and is to provide inspiration and stimulation for teachers of mathematics. As Finkel later described the founding of the Monthly,
Knowing that the status of the mathematical teaching in our high schools and academies was very deplorable and even worse in the rural schools, I had the ambition to publish a journal devoted solely to mathematics and suitable to the needs of teachers of mathematics in these schools. — B. Finkel
Apparently decrying the state of mathematics education was as popular then as now. But rather than fume and write an op-ed for the New York Times, Finkel created the Monthly. It still appears every month and contains a variety of mathematics for teachers and students at the high school and college level. The favorite pages for most, though, is the Problem section. In it you can find puzzles of all kinds, most of which don't require anything more than high school math.
A good example of a Monthly problem is this one proposed by Harry Dweighter [1] in 1975:
The chef in our place is sloppy, and when he prepares a stack of pancakes they come out all different sizes. Therefore, when I deliver them to a customer, on the way to the table I rearrange them (so that the smallest winds up on top, and so on, to the largest on the bottom) by grabbing several from the top and flipping them over, repeating this (varying the number as I flip) as many times as necessary. If there are n pancakes, what is the maximum number of flips (as a function of n) that I will ever have to use to rearrange them?
That is, imagine you have a spatula and a stack of pancakes of all different sizes which you'd like to put into order from biggest to smallest. In the worst case how many times would you have to stick the spatula between two pancakes and flip over the part of the stack sitting on your spatula? For example, if there are two pancakes, either they are in order or they are out of order. If out of order, then slipping your spatula under the stack and doing a single flip is all that's needed. If there are three pancakes, then the worst case is when the stack of pancakes from top to bottom is smallest, largest, medium. This requires three flips. In general, let's write f(n) for the number flips required in the worst case stack of n pancakes (so f(1)=0, f(2)=1, f(3)=3, etc.). Harry Dweighter is asking us to determine a formula, rule, or algorithm which computes f(n).
This is a classic Monthly problem. No fancy math, just a nifty puzzle which came to mind over breakfast. There is no expectation that this will lead to deep new math or cure cancer, just a little recreational math with your morning coffee. Amazingly enough, despite its simplicity, forty years later we still don't know how to answer Dweighter's question! Some progress has been made, though.
Two years after Dweighter posed the question, Garey, Johnson, and Lin of Bell Labs used computers and found f(n) for n up to eight. They also obtained upper and lower bounds to show it couldn't be too big nor too small. Their results appeared in the Problem Solutions section of the Monthly. It's hard to imagine nowadays that a bunch of folks at a corporate research facility could unabashedly use company time and state-of-the-art computing resources to calculate pancake flips!
What can we say about f(n)? A little thought shows that f(n) is always less than 2n. Namely, for any stack you can put it into order by first sliding your spatula under the largest pancake and doing a flip. Now you have a stack with the largest pancake at the top. Do a second flip where you flip the entire stack. Those two flips put the largest pancake at the bottom where it belongs. If you repeat this procedure on the n-1 pancakes which are stacked on top of the largest pancake while being careful to never move the largest pancake, then in two more flips you can have the second largest pancake where it belongs on top of the largest pancake. Continue in this way and you'll have the stack sorted in at most 2n flips [2].
On the other end, there are stacks of n pancakes which take at least n flips. You can see this by counting “breakpoints” between pancakes. A breakpoint happens each time two pancakes are neighbors in the stack, but aren't neighbors in size. For breakpoints we count the plate as an extra large pancake. For example, if you have three pancakes in a stack and measure them from to top to bottom, small/medium/large/plate has no breakpoints, large/medium/small/plate has one breakpoint, and small/large/medium/plate has two breakpoints. The /'s are the potential breakpoints and we get an actual breakpoint if the two pancakes at the / are not next to each other in size. If you count carefully you will see that a stack of n pancakes has n potential breakpoints. Once the stack is large enough you can cook up stacks which actually have the maximum number of breakpoints.
The key point is that each time you do a flip you can reduce the number of breakpoints by at most one. Namely, you notice that by inserting the spatula at a breakpoint you may be able to remove that one, but all the rest will remain. And, of course, if you have the pancakes in order, the stack has zero breakpoints. This means that in those large stacks which have n breakpoints even the most adroit flipper will take at least n flips to sort the stack [3].
In 1979 a research article was published by one William H. Gates of Microsoft in Albuquerque, New Mexico and Christos Papadimitriou of UC Berkeley with the fancy title “Bounds for sorting by prefix reversal”. Despite its fancy title, the paper is about the Pancake Problem. In it they show f(n) is always less than (5n+5)/3. This is a bit better than our 2n and as n becomes Brobdinagian in size, their bound does noticeably better. On the lower end, they show that whenever n is a multiple of 16, f(n) must be at least 17n/16 which, again, is a bit better than our bound. We should note that Györi and Turán independently obtained similar results by similar methods. Remarkably, the Gates-Papadimitriou bounds were the best known for nearly thirty years! It is only in the past decade that incremental improvements have been made. Even today we don't know how to compute f(n)!
So what do you do if you can't solve a problem? The Mathematician's Ruse in this situation is to distract you with a different problem. In this case Gates and Papadimitriou introduced the Burnt Pancake Problem. It's just as in the original Pancake Problem but now each pancake is burnt on one side. In addition to using your spatula to flip all the pancakes into order you must also ensure each pancake is burnt side down. If n is the number of burnt pancakes, let g(n) be the number of flips required in the worst case to sort a stack of burnt pancakes. Adapting their approach from the Pancake Problem to the Burnt Pancake Problem, Gates-Papadimitriou showed that g(n) is never more than 2n+3 and is always larger than 3n/2-1.
Gates worked on the Pancake Problem as an undergraduate at Harvard. Presumably disillusioned by fact that academics would spend their time researching (and publishing!) on the sorting of pancakes, Gates dropped out of Harvard the next year to found a scrappy little computer company. Fortunately for Gates, nobody realized at the time that pancake sorting would turn out to be the same math used in parallel computing and in DNA and phylogenetic trees. It leads to a bunch of cool ideas which we'll have to save for next month.
Bill probably is okay with missing out. After all, he can console himself by diving into his billions like Scrooge McDuck.
The Gates-Papadimitriou bounds in the Burnt Pancake Problem were the best known for nearly twenty years. In 1995 Manuel Blum and David S. Cohen, a computer science professor and graduate student, respectively, at UC Berkeley, published a paper with the straightforward title “On the problem of sorting burnt pancakes”. In it they improved the lower bound from Gates-Papadimitriou's 3n/2-1 to 3n/2 and on the upper bound they lowered it from 2n+3 to 2n-2. If n is one million, then their lower bound is 3,000,000 while Gates-Papadimitriou is 2,999,999. That these modest improvements are notable enough to be published just shows how difficult it is to compute f(n) and g(n).
The moral of the story, of course, is that if you wish to be wildly successful you should first pay your dues by sorting pancakes. Next month we'll see that besides launching careers, the Pancake Problems lead to all sorts of interesting problems in biology and math.
[1] Harry Dweighter (aka “harried waiter”) is the pseudonym of the mathematician Jacob Goodman.
[2] In fact we can do slightly better if we play close attention. For example, at the second to last step we know it takes a most one flip to sort two pancakes. Using our procedure on the first n-2 pancakes and the single flip on the last two tells us that f(n) must be no more than 2(n-2)+1=2n-3.
[3] Again we can do slightly better. If we more closely study what's going on with breakpoints we see that once n is large enough you can find a stack which takes at least n+1 flips.