Pancakes, graphs and the genome of plants

Malkevitch, Joseph (2001) Pancakes, graphs and the genome of plants. In: Robert J. Bumcrot Festschrift, 11 May 2001, Hofstra University.

Full text available as:

22 Kb


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 up on 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.

Item Type:Conference or Workshop Item (Paper)
Additional Information:This paper was given at the Robert J. Bumcrot Festschrift on May 11, 2001.
Uncontrolled Keywords:combinatorics graph theory genetics
Subjects:Q Science > Q Science (General)
Q Science > QA Mathematics
ID Code:43
Deposited By:Admin HofPrints
Deposited On:03 January 2006

Repository Staff Only: edit this item