I was going to try and explain a bit about a result called Van der Waerden's theorem
Which is one of the fundamental results of Ramsey theory,
which is an area that I'm very interested in. Van der Waerden's theorem is about colouring the positive integers.
So you take the numbers 1, 2, 3, 4, 5, and so on, and to each one you assign a colour. And
the idea is that you only have finitely many colours to use. However, you do it
it's possible to find an arithmetic progression,
that is a set of integers like 5, 9, 13,
17, 21, where the step between each one and next is the same, however long you want.
Ok, so let's imagine a game with the following rules:
we start with two
numbers - let's say 28 and 13 - and I say to you, you've got 13 colours to use.
I want you to try and colour the positive integers, that is assign one of these 13 colours to each positive
integer, in such a way that I can't find an arithmetic progression of length 28, that only uses one colour. However, you choose your
colouring with 13 colours,
Van der Waerden's theorem says I've been always going to win that game,
I'm always going to be able to find, somewhere, an arithmetic progression of length 28,
that only uses one colour. - (Brady: And it's your choice what the gap of that progression is?)
Yeah, I get to choose.
Sometimes it's called the common difference, sometimes it's called the step of the arithmetic progression. So yes, I can't tell you in advance
what the step will be. That will depend on how you choose to do the colouring. Actually I can explain that straight away. So supposing
in addition, I needed to find a progression where the step was 3 - (Brady: So 28 numbers all three apart?)
Yeah, you could easily stop that, even with just two colours.
You could colour red, red, red, blue, blue, blue, red, red, red, blue, blue, blue.
And then each number
would have a different colour from the number 3 on, so I couldn't even find an arithmetic progression of length 2 with just one colour;
if we insisted that the step was 3. So, for me to have a winning strategy
I have to be allowed to choose the step.
But if I am allowed to choose the step then I can win the game.
Well, I thought I might start with the very, very simplest case
which is: what happens if you just want to find an arithmetic progression of length 2?
So, if you just think about that for a second you realise that is actually extremely easy. Let's suppose we have two colours; red
and blue. So, without loss of generality,
one is coloured blue.
Now if I want to avoid an arithmetic progression of length 2, in one colour, I'd better colour 2
red.
And now what about three? If I colour it blue
I have an arithmetic progression of length 2, and step 2, but if I'd coloured it red
I'd have had an arithmetic progression of length 2 and step 1.
So that's not a very hard problem. As soon as you've got two things of the same colour,
so if a number of colours is
75, then as soon as you've coloured 76 numbers - then by the famous result known as the pigeonhole principle -
there must be two that are the same colour. And having two of the same colour is the same as having an arithmetic progression of
length two. The first truly interesting case of Van der Waerden's theorem is something that, I think, it's not too hard to explain,
but it's quite subtle and
the ideas that go into the proof of the whole theorem are already present in this special case.
So, the idea is actually to make use of this very simple case of
progressions of length 2, and also to make use of the pigeonhole principle that I've just mentioned,
and put them together in a clever way and then you can get, that if you have two colours
then I will be able to find a progression of length 3 that just uses one colour.
(Brady: Okay, so I've got - there's two colours being used for the colouring in and you want to find a progression of three?)
(Brady: So three numbers that have a regular step?) - Either, yeah. Regular step and either red, red, red, or blue, blue, blue.
So I'm going to show that it is impossible for you to avoid that situation if you colour enough numbers. - (Brady: Okay)
So the way to prove this - let's take a block of five numbers. Now,
what I'd like to do is focus on the first three numbers and how those are going to be coloured.
Now we know, from what we just said, that there will be two of the first three that have the same colour.
So this is actually the same argument that I've just been talking about. - (Brady: All three could be the same colour?)
Oh, yeah, all three, yes. When I say two I mean at least two
have to be the same colour now. Yep, that's an important point.
So, whatever happens, in the first three I have, I have at least two that have the same colour. So let's suppose it's this one here,
I'll just represent it by a blob rather than writing a number, and this one here. Doesn't really matter. Now if you're trying to avoid
a progression of length 3, then once you've got those two that are the same colour
that's going to force
the colour of one of the other ones. Because they were in the first three,
whichever one they, so-to-speak, point to has to be the opposite colour. So, we've got something like that.
Otherwise I'd have blue, blue, blue; with a step of 2, and I would have been very happy.
I won the game. And that wasn't the only possibility. Another possibility might have been that
the first two
were red. But in that case we could have been absolutely sure that the third one was blue.
So I'm not saying that this precise
configuration has to happen, but something like this has to happen. Within the first 5
you're going to have to have two that are the same colour,
and take the same step and reach a third one that has the opposite colour. And there's only have a certain number of ways that
you can do that. So now what we do is we divide the integers into blocks of five.
So there's 1, 2, 3, 4, 5; 6, 7, 8, 9, 10.
I'm not writing in the numbers, I'm putting dots instead. From back here
there's only a certain number of ways that we could get a configuration like this.
I'm gonna keep count - - (Brady: Okay) - ...while I do this. So it could be blue, blue, red.
Or it could be red, red, blue; or it could be blue, blue, red;
Or it could be red, red, blue; or it could be - 2nd and 3rd one blue - so
blue, blue, red; or red, red, blue. I've got up to 6. So there's 6 different ways.
So it's which one you leave out, that gives you three choices, and
whether the two that go in the other two places are blue or red that makes it up to six choices. At least one of
these six configurations has to occur, however, I colour the first five things.
So now what I'm going to do is look at these blocks. I know that each one has got one of six
configurations like this. By the pigeonhole principle again, if I colour these blocks, soon as I've coloured more than 6 of them, 2 of them
must have the same configuration of this kind. - (Brady: They aren't necessarily identical are they, but they have that killer configuration?)
They do. Actually if you wanted to, you could make them identical - and this is the way it's usually presented.
So, how many ways are there occurring the first five?
There are 32 ways of doing it. So I could, if I wanted to, fill up
33 blocks and then I'd have two that actually were coloured in precisely the same way.
(Brady: Yep) - But I'll do it this way, for today - it doesn't matter.
So that is - - (Brady: because there are only six for what we really care about, right? That's a killer moment.) - That's right
And then the other ones can be sort of - even just left uncoloured a little.
So let's just suppose that this block had a red - I'll draw it a different way now. Red,
red,
blue. And this block here also had a red, red, blue. So we know that somewhere we're going to be able to find two.
So we've got red, red, blue and we have a red, red, blue. Let's take the block
that is the same distance from this one, as this one is from this one. So go the same step.
It doesn't matter this one - I've drawn it two away, but it could have been five away;
whatever happens I just go the same step along. Now, let's try to colour this. So, so far
this is sort of, not exactly forced, but up to which one of these things I happen to choose - you're forced to have something like this.
So once you've done that let's just think how to colour this. So this one here:
well, I've got red and then I jump up by 10 and I've got red and so this one had better be blue,
otherwise, I've won the game. This one's red. This one's red. So this one had better be blue as well. What about this one?
That's blue, and that's blue, so that had better be red.
So remember this red here was a forced move? - (Brady: Yeah) - But now let's have a look. The first one here,
And then I jump up by 12 to the second one here,
and then by another 12
to the third one here. I've got red, red, red - victory.
Although what I've drawn is a special case
you can see, I think, that if it have been that configuration and they had been four apart instead of two apart or
it had been blue, blue, red and they'd been,
even sort of nine apart I could have - the same strategy of looking at the one that was the same distance along and
looking at what it had to be here, and here, and here;
one would
have ended up - actually there were two reasons this had to be red. There was this blue, blue, red; and there was this blue, blue, red.
But there's also
the red, red, red, which means that once it's been forced, then actually the game is lost for anyone who's trying to avoid a
progression at length three. - (Brady: This red, red, blue)
Brady: (configuration is not the only configuration among our six killers,)
(Brady: but all six of those killers have a similar property do they?) - All right, so maybe I could just actually
illustrate one more example. So, supposing it. it and have not been red, red, blue like that it but it has just been
first two blue and the third one red.
Supposing when I find two blocks that have the same configuration, a configuration that they share is blue, blue, red. Then so somewhere along here
I've also got blue, blue, red.
So then over here - so that blue, blue forces a red and this blue, blue forces a red.
And then the red, red forces a blue, but then I've got that one. - (Brady: Yeh)
And that one. And that one
(Brady: Ohh, the first, the second and the third, yeah)
This argument can sometimes known as the colour focusing argument, because these two colours focus on that point and force it to be red,
if you're trying to win the game, but those two focus on it and force it to be blue.
They can't be both red and blue.
(Brady: You're telling me that with a lot more paper and a lot more pens - and a lot more time this argument would work for - - Actually...
(Brady: ...19 colours and a progression of - 40 and things like that?) - Yes
so if you want to do another case, that's just a little bit bigger, maybe three colours and progression of lengths three, or
something; then it, it um
turns out to be not that much more complicated.
I won't actually
try to do it,
but I'll just say that - pigeonhole principle, what enabled us to say, as long as you take enough blocks
you can find two that are coloured in the same way, or actually as we did it two that contain the same
little configuration of this kind. For a later version you might need to have three things that are coloured in exactly the same way,
that have the same step between them.
But once you know
Van der Waerden's theorem for progressions of length three, instead of using the pigeonhole principle you can use van Der Waerden's theorem.
So, the idea is that once you've proved
some cases of and Van der Waerden's theorem,
then you can use those to prove later cases. Or,
as mathematicians will say, the argument is an argument by induction. What I've shown you is the first, not completely obvious,
inductive step of an inductive argument.
[Preview of Part 2] Explaining a maths result - sometimes, you know, some people explain something in a talk
using a board, and the ideas all seem very clear and if you go back and look at the paper,
which is the same argument but presented in a less visual form using symbols and stuff,
decoding what it says is -
can be quite a difficult process.