Hello, everyone. There's been some maths in the news this week with these headlines:
"Wikipedia-size proof too big for humans to check."
So, a Wikipedia-size proof--
hopefully more accurate than Wikipedia.
But what did they do?
Now, I'm going to explain to you what they proved this week,
and I'm going to do this through a puzzle,
and it's going to be a puzzle that we can all play,
we can all solve at home,
and you won't need a Wikipedia-sized proof to do it.
So, let's start.
So here's my puzzle.
All right. So, there you are.
Behind you, two steps behind you, is a cliff.
Two steps in front of you is a nest of angry snakes.
And not just any old angry snakes, but, like, snakes with really bad breath and stuff.
So, your torturer tells you that you can go free
if you can write a set of twelve instructions
that you have to follow
without falling off the cliff or being poisoned by the snakes.
A move is either one step forwards, or one step back.
But your torturer warns you that he might decide
to make you follow every second instruction--
instruction 2, 4, 6, 8, 10, 12.
He might make you follow every third instruction,
or every fourth instruction,
or every fifth instruction,
or every sixth instruction--bop, bop!
Can you write a set of instructions that will keep you safe?
Now, if you want to try this puzzle, do it now--pause the video or something,
because I am going to talk about the solution
after this flash.
Flash. [snaps fingers]
So hopefully you're ready for the solution now, because this problem
is actually one of those impossible problems.
So give it to someone you don't like.
Now, how can we prove
that this is impossible? Let's try that out.
So we've got twelve instructions to fill in.
OK--so one to twelve.
So let's start off with--
let's say we start off with one step forwards, because
why not?
So we're going to start with one step forwards.
Now, our next step is going to have to be a step back.
We can't have two steps forwards,
because we'll end up in the nest of snakes.
So our next step has to be
a step back, which I've put in there with a minus one.
Now don't forget, our torturer
can make us follow every second instruction.
If he does that, then you'll start with instruction two,
then it's instruction four next.
So instruction four cannot be a step back,
because you will have two step backs, falling off the cliff.
Instruction four, you're forced to find out, that it's a one--
you're stepping forwards one place.
So I can write that in like that.
But we can do the same again with the eighth instruction.
If the torturer makes you follow every fourth instruction,
then you don't want to go forwards twice.
So number eight is actually a step backwards this time.
So we can fill in all those instructions.
Those all come for free.
Now let's fill in some of these gaps.
Let's fill in the gap there in the third place.
Well, let's see what we've got here.
Step forwards--
step back--
it can't be two steps forwards next,
so this one, number three,
has to be a step back.
So I'll fill that in.
So we've got minus one there.
Now again, you could follow every third instruction,
which forces you to deduce
that the sixth step must be a step forwards. It must be a plus one.
I'll write it in.
So we've got plus one there for the sixth step.
And then, by the same logic,
if you follow every sixth instruction,
you can't make two steps forward, so number twelve
is a step back--it's a minus one.
I'm going to write that in, as well.
There we go--minus one.
Now, what else can I fill in?
I can fill in this gap here with the five.
Step forwards--step back--that's OK.
Step back--step forwards--
we can't have two step forwards here, not in a row,
so number five has to be a step back.
Number five is a step back, and then automatically you get number ten.
Number ten will be a step forwards.
So that will be with a plus one.
Let's see if we can fill in these remaining gaps.
Uh--I think, let's see--
step forwards--step back--
step back--step forwards--
step back--step forwards--looks fine to me.
We can't have two step backs here. This must be a plus one.
Let's fill this in.
And in the same way, number nine here
is a minus one.
And number eleven is a plus one.
So you fill in these instructions.
Now, all of this was forced on me--there was no free choice here.
But, if you look
at every third instruction--
so at three, six, nine and twelve--
you go step back--step forwards--good.
Step back--
step back again--
whoops-a-daisy, fall off a cliff.
So you are forced
to fall off a cliff.
These were the only instructions
that you can really come up with,
and still you will die.
So you'll find out that it's an impossible problem.
But, this is quite nice--
if I remove the last step there, number twelve,
so we just have the first eleven steps,
then those instructions
do work. Those eleven instructions will keep you safe.
So if you want to give this puzzle to someone you like,
ask them to give
eleven moves, instead of twelve.
So that's what happens when the cliff and the snakes are two steps away from you.
So what would happen if the cliff and the snakes were three steps away from you?
How many instructions would your torturer force you to write
so that he can guarantee
that you'll die?
So this was an open problem,
but it was solved this week
by these two guys from the University of Liverpool,
and they worked out that the solution
is 1,161.
So if your torturer
makes you write 1, 161 instructions,
then he's guaranteed to have at least one subsequence
that will topple you over the cliff with three steps.
Now, that does also mean
that there is a sequence
of 1,160
that will keep you safe.
And here's one of them.
[music plays]
So to prove this result took them six hours using computers.
They didn't say how many computers they used,
but they generated a 13 gigabyte file,
which they compared to Wikipedia, because apparently
the text for Wikipedia is a 10 gigabyte file,
and they claimed it was the longest proof ever.
It's an example of a computer-assisted proof.
It looks like a clever kind of brute force.
I tried to read the paper, but I'm not a computer scientist myself,
so I didn't quite get it.
So if you want to read the paper,
I'll put the link in the description.
Now, what we've shown is
if we have the cliff
two steps away,
we can kill the guy.
If we put the cliff
three steps away,
we can kill the guy,
if we have a long enough sequence.
So is this always true? Is this true for any number?
This is called Erdős Discrepancy Problem.
It was proposed by the Hungarian mathematician Paul Erdős
in the 1930's.
These guys from the University of Liverpool are already working on the next step.
So imagine the cliff now four steps away.
They're trying to work out
how many instructions you need to
guarantee that you can kill this guy.
But we're going to need a smarter way to solve it in general.
We can't just check every number in turn.
So why do this?
Well, I could talk about discrepancy theory,
and wireless communication,
and cryptography,
and applications like that.
But the real reason we do it is because it's a hard problem,
and the methods we develop
to solve this problem
could then be used in other problems.
Perhaps more important problems.
It adds to our knowledge of the world.
Now, they are working on the next step.
Imagine the cliff four steps away from you.
They haven't yet found what length sequence you need
to guarantee to kill your victim,
but they have found a sequence
of 13,700
that will keep you safe.
So any subsequence will never be longer than four,
so you can avoid the cliff,
and you can avoid the snakes.
I'm going to show you what that sequence looks like.
It's going to scroll past.
It's going to take about a minute.
So, for now,
if you have been,
thanks for watching.
[music plays to end of video]