Sort a stack of pancakes by size using nothing but a spatula flip
A short-order cook stacks pancakes of all different sizes in a messy pile. The only tool available to straighten them into a neat stack — largest on the bottom, smallest on top — is a spatula that slides under any point in the stack and flips everything above it over in one motion. Given a stack of n pancakes in the worst possible order, what's the fewest flips guaranteed to sort any stack of that size?
Reveal the answer
Nobody knows the exact answer for every stack size — it's still an open problem in computer science. The question was posed anonymously (under the name 'Harry Dweighter') in the American Mathematical Monthly in 1975; in 1979, undergraduate Bill Gates and Christos Papadimitriou co-authored a paper proving flip counts between 17n/16 and (5n+5)/3 — the only research paper Gates ever published, years before founding Microsoft.