The Pancake Problem
----Keesje 't Hooft (Y13)
Abstract
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 at 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, how many flips (in terms of n) are required in the worst case? Jacob Goodman posed this question in the American Mathematical Monthly journal under the pseudonym Harry Dweighter (Harried Waiter) in 1975. Since then, there have been numerous academic papers on the subject along with variations to the initial question. To begin tackling the problem, we shall call the maximum amount of flips for n pancakes the pancake number, P .We can calculate P for small values of n ourselves. For n=1, there is only one pancake so we don’t have to do anything to it in order for it to be ordered correctly, so P 1 =0. For n=2, either the largest pancake is on the bottom, in which case we will not have to make any rearrangements, or the largest is on the top where we will have to make a single flip to order them correctly. Since we are looking at the maximum number of flips, we will take P 2 to be 1. Now we move onto n=3. Below is a picture showing all possible ways to arrange three pancakes and how many flips are required for each scenario.
41
Made with FlippingBook - Online Brochure Maker