As it is Shrove Tuesday I thought I would briefly introduce the computer science problem of pancake sorting, which incidentally is the subject of Microsoft’s Bill Gates’ only (I believe this to be true anyway) academic paper. If you are interested, this paper is available online and is relatively accessible for an academic paper.
I first came across this problem in 2014 when Simon Singh published an article in the Guardian – as Simon Singh another famous person, David S Cohen, a co-creator of Futurama also has a published paper on a harder varied of the problem known as the “Burnt Pancake Problem”
I guess, I should probably describe the problem now…. In it’s traditional form, it was stated by the original proposer of the problem, the mathematician Jacob Goodman (writing under a pseudonym at the time) as follows:
“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, what is the maximum number of flips (as a function of n) that I will ever have to use to rearrange them?”
This is one of those classic problems that is deceptively easy to state but very hard to solve – in fact Wikipedia tells me that last year a team of scientists determined the minimal number of flips required was proved to be NP complete but i haven’t read that paper yet.
Conceptually some rough estimates on the upper bound for the number of flips required for flipping n pancakes are quite easy to arrive at – e.g. it can not require than 2n flips. I think it would be fun to talk about this with a school class – I certainly wish I had thought about it earlier today and spoken to my A-Level class about it.