Before Microsoft, Gates Solved A Pancake Problem

Copyright © 2008 National Public Radio®. For personal, noncommercial use only. See Terms of Use. For other uses, prior permission required.

RENEE MONTAGNE, host:

Hope you're enjoying your breakfast. If it happens to be pancakes, give a thought to Bill Gates. Today he's settling into life after Microsoft. But in his life before Microsoft took off, a much younger Bill Gates spent some time thinking about pancakes, an untidy stack of pancakes. He even published a mathematics paper about it. And academics say it was a fine peace of work. NPR's David Kestenbaum reports from the Lincoln Waffle Shop in Washington, D.C.

DAVID KESTENBAUM: I need a stack of pancakes.

Unidentified Man: OK. Would you like butter?

KESTENBAUM: Sure. I need a big stack of pancakes.

Unidentified Man: Sure, thank you. I got you.

KESTENBAUM: All right, so the problem Bill Gates was trying to solve was this. Imagine you work at a diner and the cook is really fast but he's not the most organized guy. And when he piles up the pancakes, sometimes the biggest pancake is on top and the smallest one is in the middle and it's just a mess. So your job is to sort them using a spatula.

And you can only put the spatula in someplace in the stack and just flip the pancakes above you. And you have to figure out a series of flips that will sort the stack so that you get the biggest pancake on the bottom, the second biggest one above that, all the way up to the smallest one on top, so that you can present it to the customer in a nice pile. It turned out to be a very difficult math problem.

Professor HARRY LEWIS (Harvard University): The question is, if there are N pancakes - where N is 73 pancakes or 12 pancakes or whatever - what's the minimum number of flips that suffice always to sort the stack.

KESTENBAUM: Harry Lewis is a professor at Harvard University. And back in the 1970s he gave this puzzle to his combinatorial mathematics class. Just an example of a problem that was easy to describe but had not been solved.

Prof. LEWIS: So I posed it in class and then I went on. And a day or two later, as I recall, this smart sophomore comes into my office and explains that he's got a five-thirds N algorithm.

KESTENBAUM: The student with the five-thirds N algorithm was Bill Gates. So what does five-thirds N mean? Well, there's a fairly simple way to sort the stack, but it would require two flips per pancake - two N. Basically, you start by sticking the spatula under the biggest pancake, flip it and the stack above it, which puts the biggest one on top. Then you flip the whole stack, putting the biggest pancake where you want it, on the bottom. Then you repeat this for the second largest one, etc.

Anyway, Gates had a better procedure. Instead of requiring two flips per pancake in the stack, it required five-thirds, or 1.67 flips.

Prof. LEWIS: And it involved a complicated case analysis of what exactly the configuration of the top few pancakes might look like and so on. It was very - it was quite clever.

KESTENBAUM: Bill Gates worked on it with a young assistant professor at Harvard, and in 1979 the research got published under the title "Bounds for Sorting by Prefixed Reversal."

Prof. LEWIS: I think the problem remained pretty much in that state for 30 years, and then just recently...

KESTENBAUM: Some researchers found a slightly better sorting strategy, but it's only 1 percent faster. And they figured it out only with the help of powerful computers.

Prof. LEWIS: You know, I have to look at this paper and laugh. You know, they never could have actually done the case analysis were it not for the computer industry that Bill Gates built in the intervening 30 years.

(Soundbite of laughter)

KESTENBAUM: Lewis looks back on this story with pleasure. It was a brush with a kid who would shape history, even if it wasn't in the lofty realm of mathematics.

Prof. LEWIS: We who've spent our careers in academia consider this the highest calling known to human kind. We'll say, you know, that this really proves that Bill could have done something important and noble with his life. That's a joke. I do believe that he's done something enormously important and increasingly noble. But yes, you know, if he'd wanted to, he could've been a mathematician. Thank goodness he didn't choose that path.

KESTENBAUM: Lewis won't say what grade Bill Gates got in his class, but he says Gates did well.

David Kestenbaum, NPR News.

Copyright © 2008 National Public Radio®. All rights reserved. No quotes from the materials contained herein may be used in any media without attribution to National Public Radio. This transcript is provided for personal, noncommercial use only, pursuant to our Terms of Use. Any other use requires NPR's prior permission. Visit our permissions page for further information.

NPR transcripts are created on a rush deadline by a contractor for NPR, and accuracy and availability may vary. This text may not be in its final form and may be updated or revised in the future. Please be aware that the authoritative record of NPR's programming is the audio.