These steps can be used to set a limit of how many flips required. If a stack of n pancakes are disordered to a large degree, it will require two flips for every pancake and by the time the second smallest pancake is in the right place, the final pancake must be in the right place. This means the upper limit must be 2(n-1). Now that we have found an upper limit, we need to find the lower limit as well. To discover this, we will look at the problem in a different manner: adjacent pancakes. In an ordered stack, {a,b,c,d}, all the entries are adjacent. This will be a definition for an ordered stack, and no or few adjacent entries will correlate to a disordered stack. Therefore, to arrange pancakes in a disordered stack with no adjacent entries to an ordered stack, you must produce n-1 pairs of adjacent entries. Since a flip can only produce at most one adjacent pair of entries, this means the lower limit for maximum flips is n-1. However, if the nth entry needs to be put at the bottom, which is required for some permutations, that does not increase the number of adjacent pairs. This means that our lower limit should actually be n flips. How do our limits compare to the pancake numbers mentioned earlier in the piece? If we take n to be 17, the pancake number will be between 17 and 32. That is quite a large range that gets us no closer to our target of predicting the number of maximum flips required. Bill Gates, in his only published paper, gets us closer to this answer. He found that the upper limit for the maximum number flips is (5n+5)/3. Since his paper was published in 1979, there have been significant improvements. The lower limit was shown to be 15n/14 and the upper limit to be 18n/11. This narrows the range to between 18 and 30. Not only is our chef unable to order pancakes, he also burns a side of every pancake. As a waiter, I must make sure all the burnt sides are facing down. So the pancake sorting problem just got a whole lot more complicated. Harry Dweighter has to work out the maximum number flips required to order pancakes in terms of size and with their burnt sides down. A stack of four burnt pancakes prepared by the chef might look like this , where a line above indicates the pancakes burnt side is facing up and a line below indicates the burnt side is down. The waiter wants to get the pancake ordered like this , with only doing flips similar to what he was doing to order the pancakes earlier. This can be done in 3 steps: Variations on the initial problem
43
Made with FlippingBook - Online Brochure Maker