So today I want to tell you about the
pancake number, which is among the most
ridiculously named numbers in maths but
it is technically to do with pancakes - or
at least pancakes are one nice way to
explain what this number is. We have a
pan full of pancakes here, and the idea
with this is they're not all the same
size, so have five different sizes of
pancake; and we also have a very
inconsiderate chef who makes pancakes
all different sizes and then serves them
up in the wrong order. Because I'm sure
you'll agree if you've got a stack of
pancakes of all different sizes the most
satisfying way is to have them in
decreasing order of size with the
smallest one at the top and the biggest
one at the bottom. So we need to try and
get this stack of pancakes back into
order. So I stick it on a plate. I'll use my
pancake flipper. - (Brady: Safety first)
Yep. So stick that on a
plate. So the question now is how do we
put these pancakes back into the right
order? There is a rule about how I'm
allowed to shuffle these around: I'm
allowed to take the top section of
pancakes and turn it over, and that's all
I can do. So in this case, what do I
want to do? I want to flip maybe the
whole thing? Yeah I want to flip the
whole thing - no in fact first I'm gonna
flip these top two. And the reason for
that will become apparent shortly, so I
do that, so that's one flip. And I'm now
gonna flip the whole thing - there we go.
And now I'm gonna flip - oh
I shouldn't have flipped the top two!
I'll figure this out eventually. So I
flip those three, that's three flips. I
now flip the whole thing again, that's four flips.
And if I hadn't flipped those top two at
the start I would have had not to do
this now, but nevermind. So that's five
flips, which is fine because I know that
any stack of pancakes can be fixed in
five or fewer flips. This one, I suspect,
could have been in slightly few of
five but, in this case I've used exactly
five which is within the bound so that's fine.
So any stack of five pancakes can be
done in five or fewer flips. There are
obviously some that- well this is
currently in the state where it needs zero
flips; but they're obviously some
that can be done in fewer than five and
the most you'll need for five pancakes,
doing it in the most efficient possible
way, is five. So the pancake number, for
five pancakes, is therefore five. And
this works for any number of pancakes in
a stack, so I can show you what happens
with three pancakes. There are
six possible orderings for three
pancakes: so I could have small medium
large, three at the bottom again but
instead have two and then one. Two at the
bottom, then three, then one - like that. One
at the bottom and then two and then
three. Two at the bottom, one, three - like
that. And finally one at the bottom, three,
and then two. That gives me all six
possible orderings. And for each one of
these I can work out how many flips I
need to get it back into the- the sort of
standard correct way up. So in this case
it's zero flips, it's already there. This
can be done in one, which is just to flip
the whole thing. This one can be done in
one flip. This one; if I flip those top
two and then flip the whole thing I'll
get back to sorted, so I'm going to call
that one two flips. This one if I flip
the whole thing, and then flip those top
two around, that'll be two flips. And in
this case - this is the most difficult one
because this can't be done in fewer than
three flips. So I can do it in three;
I would maybe say flip the whole thing
and then you flip the top two and then
flip the whole thing. But it can't be
done in fewer than three, so for three
pancakes the pancake number is three. - (Brady: I'm seeing a trend-)
Yes it does look a little bit pattern-y! So
for three it's three, for four it's four,
for five it's five. After that it starts
to go on, so every so often it goes up by
two instead of going up by one; so it's
not quite always just the number of
pancakes that you've got. But it is
actually something that people try and
calculate - they try and work out what is
the pancake number for a given number of
pancakes. And it's actually an ongoing
question, because for 20 pancakes we
don't know what the pancake number is. - (Brady: No!)
No it's it's an open question in maths.
We don't actually have- 20 or above we
don't actually really know that what the
answer is to this. And I guess it's
partly because it's just a massive
computation. If you've got 20 pancakes in
a stack, the number of possible ways you
could order 20 pancakes in a stack is
massive. For any given ordering the
number of possible sets of flips you
could do is even massiver. You know,
to check all of those and see which one
is the most efficient would take a lot
of computer time, so no one's managed to
crack that yet. - (Brady: What is it for 19?)
For 19 it's 22 I think?
Something like that. So yeah it's- we
know it's more than 22; and in fact we
know it's less than, I think 35? And the
reason- the person that we have to credit
with the the fact that we know it's less
than 35 is Bill Gates.
So Bill Gates, that- the guy off of
Microsoft, when he was at university in
1979, when he was 24, he did a paper.
Unfortunately the paper wasn't called,
like, 'On the Pancake Number'; it was called
something like 'Algorithms for Prefix
Reversals' because that's the the
technical computer science term for this.
If you're taking the first section and
reversing it,
that's a prefix reversal. And his paper,
they proved that there is an upper bound
for the pancake number. For- if you know
how many pancakes you've got, what the
upper bound is for n pancakes. So I
think for n pancakes they prove that
it's 5n plus 5 over 3. Which means that
for 20 pancakes it's 105 over 3, that
means it's 35. That is thanks to Bill
Gates; since then they've actually worked
out a better upper bound for it that's
slightly nicer. They've now shown that
anything is less than 18n over 11,
which was found in 2009 which was
exactly 40 years later they managed to
improve on that bound. So there is a way
that will always work, for any given kind
of messed up stack of pancakes. So the
trick is that you take whichever pancake
is the biggest pancake that's not
currently where it's supposed to be and
put it to the top. And then I put that
one to where it's meant to be. If you
keep repeating that so if now, say if
pancake 3 wasn't in the right place you
do the same thing - you put it to the top.
And then each time you you're kind of
definitely gonna place at least one
pancake, possibly more if you're lucky.
You will always do it in 2n minus 3, so
for n pancakes. In the case of 5 it would
always do it in 7 or fewer, but I know
that for 5 pancakes the pancake number is
5, which means there is a way to do all
of them in five or fewer. So that
wouldn't be necessarily the most
efficient method. The nice thing about
this is it actually originated from like
a real world problem. So there was a
mathematician, Jacob Goodman, who was
trying to solve a problem in the real
world and this thing occurred to him as
like, oh that's an interesting puzzle - you
know how can I- how can i find how many
flips it takes to do this? And he wasn't
actually using pancakes at the time. It's
really unfortunate, he wasn't in a
kitchen, you know, cooking pancakes and
discovered this. He had a stack of towels
in the cupboard - it was a really domestic
math problem - and he had to try and put
these towels in the cupboard. But he just
had a shelf and there wasn't any kind of
surface nearby and he needed to change
the order of the towels so he could just
take the top of the stack and flip it
over. And he kind of was like actually
that's that's quite a
nice problem and he wanted to write it
up for a magazine for American
Mathematical Monthly. And he was like, oh
how can I reframe this so that it's a
nice accessible thing? And this idea of
using stacks of pancakes with a flipper
was his- his way into this. He used a
pseudonym, he wrote an article under the
name of Harry Dweighter, which is 'harried
waiter' who's carrying the pancakes and
so on. And it was, you know, it was a nice
little here's a problem, people
responded to it and wrote back and stuff.
So that was how the the thing kind of
first originated, but it's since it's
become like a real thing and people work
on it, people publish papers on it. So
there's a chap called David Cohen who
writes for The Simpsons who's a
mathematician, a computer scientist - in
his spare time when he's not writing for
The Simpsons. I guess he trained as a
computer scientist and while he was
studying he also did a paper on this,
which was on a thing called the Burnt
Pancake Problem. And in that case you've
got pancakes where one side of the
pancake is burnt, and you want to end up
with them all in the right order in the
stack, but also all the burnt sides down
so that no one can tell that you've
burnt all your pancakes on one side. And
that makes it slightly more complex and
it means that you have to make sure that
you do all the the steps in the right
order and you might find that you've- you
know, you've done it right but they're
all upside down and you need to redo the
whole thing. So that's another thing that
he's kind of published a paper on and
that's a separate but related problem, I
guess. - Brady: You know I'm glad you watch
videos here on YouTube, but sometimes you
want to go a bit deeper than these
tempting nuggets of information we give
you. And that's where the Great Courses
Plus can come in. These on-demand videos
can be entire lectures or entire courses
full of videos taught to you by leading
experts from around the world. There's a
boat full of brilliant courses covering
all sorts of mathematical subjects of
course. I've spoken about these before,
I'm sure they'll appeal to Numberphile
fans. But it's not just mathematics; you
name it and they'll cover it.
Sometimes when I'm just grazing on the
Great Courses Plus, what I like to look
at is geology and geography - things like
this. Whatever your little niche interest
you can go really deep here on the Great
Courses Plus. For a free one-month trial
go to thegreatcoursesplus.com/numberphile.
That's a free one-month
trial, there's the address on the screen.
TheGreatCoursesPlus.com/numberphile.
Give them a look, I'm sure
you'll like them, and our thanks to them
for supporting this video.