Pancakes, Graphs, and the Genome (UMAP)

In 1975, Jacob Eli Goodman posed the following problem in the American Mathematical Monthly under the pseudonym of Harry Deweighter ("harried waiter"): 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 upon top, and so on, down to the largest on the bottom) by grabbing several from the top and flipping them over, repeating this (varying the number 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 shall ever have to use to rearrange them? What is exciting about this problem is that not only is it a problem in pure mathematics of great charm, but also it has led to a variety of ideas of great applicability. Furthermore, the original problem Goodman posed is not completely resolved despite the simplicity in stating the problem. The purpose of this note is to survey some of what is known about the pancake flipping problem, to suggest some projects that might make interesting work for high school students and undergraduates, and to show how questions such as this are valuable ones to show students in a wide variety of classroom settings. The problem connects with many important and fundamental ideas in computer science and mathematics and affords an illustration of how these ideas can be looked at in an attractive context.

Table of Contents:

INTRODUCTION

NOTATION, BACKGROUND, AND EXTENSIONS

HIGH SCHOOL OR UNDERGRADUATE RESEARCH PROJECTS

WHAT IS KNOWN?

APPLICATIONS TO COMPUTER ARCHITECTURE

APPLICATIONS TO MOLECULAR BIOLOGY

REFERENCES

ACKNOWLEDGMENT

ABOUT THE AUTHOR