Math's problem, a maths problem which was

Related to the four color theorem

Which is something I've mentioned before, perhaps I should do a quick recap of what the four color theorem was.

It's a similar sort of thing really. Before color theorem said, imagine you had a map

Right, and I'm just going to make up some sort of map here. And the idea was, I want to color in this map

So that neighboring countries are not using the same color

So if I color this in, it might be kind of this bit here, the idea being that any map can be done

Using four colors or fewer, or in other words, there aren't any maps that need five colors. So that's true

That's a fact right, that was proven in the 1970s. But this problem that I'm going to talk about today, comes from the

1950s and it's not something that's been solved yet. It's called the Hadwiger-Nelson problem, catchy name

And I'm going to try to quote you what the problem is

How many colors are needed to color the plane?

So that no two points at unit distance are the same color. That's very formal

So let me just break that down. What it really means is imagine,

I'm somewhere on this map here. So there I am and I'm going to go for walk

I'm gonna take a step and my step is going to be one unit

So these might not be countries anymore because I'm changing the scale of this. So we're taking a walk and I want to go

One unit. Maybe that's one unit. Whatever that means and then take another step and I'll take one unit step

But every time I take a step, I want to step on to a different color. I want the color to change each time

I step so I'm gonna go for a walk. I want to change the color change the color, okay change the color again

I could step back to here, change the color again

Change the color again. I could go over here, but then for example

I couldn't walk this way. Should I take a one unit step over here, I wouldn't be changing the color

So the question is, is there a way to color the plane. So imagine this as an infinite map

Is there a way to color it so that I can take a walk always changing the color?

Can I do it so I can take any walk?

So any walk that I care to do, I will always be changing the color with each step I take, and that's the question

brady: No matter what direction you go. No matter what direction you pick no matter what walk that I choose to do

Every step lands on a different color. Well for starts

There is a solution to this, as seven colors work

We can do it with seven colors, and we can prove that really really quickly. You take the infinite plane

We're going to tile it with hexagons. So I've got now a little unit of hexagons

I got seven hexagons there and I've used seven colors and now I'm just going to repeat this over and over

So I'm going to repeat this

So I'm creating a pattern of colors with my hexagons.

Now All I need to do to solve this problem, is imagine the diameter of those hexagons was less than one

Slightly less than one, that means that every step I take would be on to a different hexagon

So I could start here, and every step I take would have to be on a different hexagon, which is a different color

I just add one thing though. We wouldn't want to step from this purple hexagon on to the next purple hexagon

which means I want this distance to be greater than one, which means the diameter of your hexagons needs to be less than 1,

and greater than .76

Fine. That's all you need so take the hexagons to be .9 and

The problem is solved you can walk around that hexagon

Infinite plane and change the color with each step

Brady: and even if I wanted to step on one of the same color, couldn't do it

Even if you wanted to, even if you tried you can't because those hexagons are chosen so that you can't step onto

The color that you're on. Brady: Cool. What's the problem? Exactly, What's the problem?

So we definitely have a solution, and it can be done for seven

So the question is can it be done for six colors, or can we do it with five colors?

Four, three, two, right?

How many colors, what's the fewest colors we can do this with?

So we can eliminate some of the answers really quickly. You can't do it with two, I'll show you that

So imagine we try to do it with two, so all I'm going to draw out is the walk

I'm just going to draw a walk. So I'm walking in a triangle an equilateral triangle. now, let's try and color this walk

So say I start in the green region, and then take a step and I want it to change color

So now I've stepped onto a blue region then I want to take another step, and I want to change color now

I've only got two colors available

So I'm gonna have to step onto a green

Region here. But that means if I want to step back to where I started, and there's no reason why I can't do that

I'm not changing the color

I'm stepping from green to green, that's not allowed. this is an example of a walk that can't be done with two colors

It can be done with three colors, but it can't be done with two. What about three?

Well again, there's an example it shows you can't do it with three

So same sort of idea. Here's a specific example, every step there in that shape is one unit. So you're walking around that path

Great, but can I do this with three colors? Let's start with green and then I move on to the next step

Well, it might be blue. Now, I want to step here. This has to be a different color. So let's have a different color

let's have red, now if I want to step on to the next one

Where it can't be red

So let's make it... oh it can't be green as well because I don't want to step back to the green

So it has to be blue. So that one's pretty okay. Now what if I take another step?

I think I've got a choice here.

I now think I can choose my color

I'm gonna choose green here for the middle, now for this if I take one step up, oh it can't be green

It can't be blue. So it's red. And if I step down to here, it can't be blue, green or red

So I need a fourth color. I can't do it with three.

It can be done with four and then, that's where we got to. 60 years ago

That's as far as we got, we showed that it can be done with seven

It can't be done with two, it can't be done with three

So maybe it could be done with four, five, six, and seven we know is definitely true. And that's where we were

60 years, until recently.

So in 2018 an amateur mathematician found a walk, an example of a walk that can't be done with four

Which means it can only be done with five, which means four is not a solution. So we've eliminated four colors from this problem

So I call him an amateur mathematician. I think that's a bit of a disservice

This is a person called Aubrey de Grey who is a biologist who's famous in his own right in his own field

He works in anti-aging, he's a very interesting guy

Himself, but he does maths for fun. And this was a problem he was trying to do, for fun

And so he came up with a walk that can't be done with four colours and what he did is, he took

This example, it's got a name

It's called the Moser spindles, strange name, and he made copies of that which he fused together

So he fused together lots of copies of this, and he created this monster, this monster Network

20,000 points

Huge thing, and then he got a computer to show

that

Four colours are not enough. It can't be coloured in with four, and it can be coloured in with five

Fantastic, we eliminate four

For the first time in sixty years. He then improved that, he wanted to find a smaller example

Smaller than this monster and he got an example that's I think

1581 points so that's much better right so a much smaller example, but it's the same thing

It's an example that can't be colored with four colours

Can be done with five

so then he published this and

Mathematicians got stuck in they said well, can we do better? Can we find a smaller one the smallest we found so far is

This one here. So this is a walk found by Martin hooli

Who we have mentioned before, we talked about this guy and he colored in the Pythagorean triples

We did a video about

Pythagorean triples and coloring them red and blue, it's a similar sort of problem and he found this example

It's a walk with 533 points that needs five colors

So we've got red, green, blue and yellow

And then the fifth color is white, which is used only once, right there in the center

This episode has been brought to you by brilliant, the website that's full of

Questions and quizzes and puzzles and courses and all sorts of things to make you smarter

You're seeing some examples on the screen right now

They have all sorts of new things every day

But they're not just dumping stuff on the website, all sorts of weird conundrums for you to solve

Everything on brilliant has been designed with a purpose in mind, and that's to really make the people using it

Smarter, to change the way you think, to make you a bit of problem solver

It's really about enriching the people who use brilliant. Not just giving them questions and then marks out of 10

There's loads of stuff on the brilliant site You can look at for free,

So go ahead and do that.

If you sign up for their premium subscription,

Which gives you access to everything, You can get 20% off that by going to brilliant.org/numberphile .

20% off and they know you came from here. Now if I've done my job correctly,

The URL should be down below me right now, and down in the video description.