Tech WondersPlay

Algorithms & EmergenceAlgorithms

Bill Gates' Pancake Problem

His only research paper was about flipping pancakes

A messy stack of pancakes, one spatula, and only flips allowed. How few flips can sort it, and why did Bill Gates care?

You'll find out

  • How few flips can sort a stack
  • What a young Bill Gates proved
  • Why the exact answer is still unknown

Why it matters

Sorting with one awkward move shows how quickly “fewest steps” questions get hard, even for computers.

About 3 min6 interactive slides · 5 questionsLesson 243 · Zone 27

Play this lesson

Free to play in your browser or on iPhone

More in this zone

  1. 235Wireless SecurityThe Relay TheftThieves can stretch your car key's signal from inside your house
  2. 236Distributed SystemsThe Byzantine GeneralsHow do you agree on a plan when some messengers lie?
  3. 237RelativityTime Runs Faster UpstairsAtomic clocks tick faster just 33 centimeters higher
  4. 238Phase TransitionsWater That Freezes on CommandA quiet liquid can stay below freezing until something disturbs it
  5. 239Threat AnalysisThe 99% Test That's Usually WrongWith a rare condition, most positive results can be false alarms
  6. 240ConcurrencyDeadlockTwo programs can wait for each other forever
  7. 241Wireless CommunicationWhy Wi-Fi Slows Down in a CrowdOnly one device can speak on a channel at a time
  8. 242Computational PhotographyPanorama GlitchesMoving people turn into monsters in panoramic photos