Red & Black Knights (extraordinary result) - Numberphile

0:00 Remember one of the first videos we did together was

0:03 about a knight that gets trapped and we can't repeat square.

0:06 We have to always go to a new square.

0:09 The night is moves around on a square spiral in an infinite chessboard.

0:13 And we've numbered the squares and you start at zero.

0:22 So I'll put a penny where you've been.

0:27 And where you move to has to be the lowest square that you haven't visited.

0:33 Lowest.

0:32 The lowest.

0:33 The smallest number you haven't been to.

0:35 So from zero, we could go to 9, 11, blah blah blah.

0:39 So he goes here.

0:40 Okay.

0:41 Now, where does he go?

0:42 I put a penny to mark where he started.

0:44 He can go to two and and so on.

0:48 And he keeps going.

0:49 From two, he can go to five.

0:51 From five, he can go to eight.

0:53 He can't go back to one he's been to.

0:55 That's right.

0:55 It's got to be a new square, an unoccupied square.

0:58 From eight, he can go to three, and from three, he can go to six, and from six,

1:02 he can go back to So, he's filled in one,

1:05 and then he fills in four, and he keeps going.

1:07 So, so it looks like he he's going to go on, but in in fact,

1:10 after a while, he runs out of squares to go to.

1:13 He gets trapped.

1:14 He ends up at a square where all

1:16 of the eight things he could move to, he's visited already.

1:19 So, it's a finite sequence.

1:21 The sequence of squares that he stepped on.

1:23 Today's video we have a lot of knights, not just one.

1:26 And we put them down in a way they are courteous knights,

1:30 very friendly, gentlemanly knights, and they don't want to attack each other.

1:36 They want to keep their distance from all the other knights.

1:39 And we we just put them down.

1:40 The rule is you walk along the spiral and when you come

1:44 to a square if it's not in the domain of any existing knight,

1:50 if it's not being attacked by any existing knight, you put a knight there.

1:54 So that we put a knight at zero.

1:56 That's a knight on zero.

1:57 And we will go around the spiral.

1:59 Now we come to square one.

2:00 Now square one is not attacked by any can't see any knights from it.

2:04 This knight is not a knight's move from that.

2:06 We So we can put a knight there because the first knight couldn't catch him.

2:10 The first knight couldn't catch him.

2:11 It's not in the domain of any existing knight.

2:15 Right?

2:15 Now we come to two.

2:16 Two isn't two is also unattacked and three is unattacked.

2:21 Four would be attacked by this knight on square one.

2:24 So we can't put a knight on four.

2:26 So we we can't put knights at 12 because of that or 13 14 15.

2:31 No.

2:32 The first one we come to.

2:33 No.

2:34 16 is is attacked by that.

2:36 17 18 19 20 is the first time we can put down another knight.

2:41 All right, let me keep going.

2:43 25 is free.

2:45 So, we put a knight at 25.

2:46 26.

2:47 No, no, no, no, no.

2:48 30 is good.

2:49 31, 32, 32, they're all attacked.

2:52 35.

2:53 Well, it's really interesting because you start thinking, oh, hang on now.

2:56 That one's going to catch that one.

2:57 And that like they all start coming into play in different ways.

3:01 Yeah, it's complicated.

3:01 We get some interesting patterns which you you might think

3:05 would be random or they you might think they'd be regular.

3:07 Well, you'll see what happens.

3:09 40 is okay.

3:10 Nobody is attacking 40 or 41 or 42.

3:14 49.

3:15 They're all good.

3:17 Woohoo.

3:18 53 is out.

3:20 Yes.

3:21 And 54 is okay.

3:23 And 65 is 64 is not, but 65 is free.

3:28 So, we got a cluster of five.

3:30 We can't do 67, 68, 69, 70 we can do.

3:34 And we've filled up a cluster of five and so on.

3:38 And it keeps going.

3:39 We got a cluster of four in the middle.

3:41 And then we get clusters of five around it.

3:44 And that pattern sort of continues.

3:54 And here's a picture of what it looks

3:56 like after about a thousand steps of the spiral.

4:01 And you can see it's periodic in a a very precise mathematical sense.

4:07 In this quadrant, we have clusters of five separated by single knights.

4:14 Upon this vertical line,

4:17 we have clusters of 2 4 2 4 2 4 that keep going forever.

4:21 And similarly in all the others.

4:22 So, so this is a periodic structure.

4:25 Pretty but regular.

4:27 So, it's pretty nice.

4:28 But if we have knights of two colors,

4:30 something totally different and unexpected and amazing.

4:34 Red and black knights.

4:36 All right.

4:37 And they take turns.

4:38 And the rule is when it's black's turn to place a knight,

4:41 he places a black knight at the first

4:44 square that isn't attacked by a red knight.

4:46 They don't mind collaborating.

4:49 Black can be knight moves from black knights but not from red knights.

4:53 So if I'm on a spot and I'm a black knight,

4:56 it's okay if a black knight could catch me because he won't catch me.

4:59 He won't.

4:59 They were we're friends.

5:01 We got two armies really.

5:02 They got the black knights and the red

5:03 knights and they're they're really competing for Europe.

5:06 You have to think of the great plane of Europe and um these are the knights.

5:11 Neil, who even thought of this doing this?

5:13 Jonas Carlson in Sweden sent me a letter with describing some some

5:18 interesting problems that he'd been looking at and this was one of them.

5:22 And he said, "This this blows my mind.

5:25 This is so incredible." He started off, as I just did with you,

5:29 with black knights, and we get a periodic structure.

5:32 No mystery at all.

5:33 But wait till you see what happens with the red knights.

5:36 Oh.

5:36 Oh, boy.

5:38 So the rule is you go around the spiral again and you place a black knight

5:42 on the first square that is not occupied and is not attacked by a red knight.

5:49 Red gets to play.

5:50 They take turns.

5:51 Red puts down a a red knight and the first square.

5:55 It can be attacked by a red knight,

5:57 but it must be unoccupied and not be attacked by a black knight.

6:02 Reds and blacks are very respectful of each other.

6:06 Black goes first and puts his knight at the lowest square, not occupied.

6:10 Okay, red goes next.

6:12 One is free.

6:13 It's not attacked by that black knight.

6:16 So, it goes there.

6:17 Black's turn to play.

6:18 Black claims that square three is not attacked by a black knight.

6:24 Black's turn to play.

6:25 Black would ideally like to place a knight there,

6:29 but that square is under attack by that red knight.

6:32 So, it can't go there.

6:33 So it goes to the next one that it can.

6:35 Now it's red's turn to play.

6:37 This square was attacked by this red knight, but that is fine.

6:41 The red knights collaborate, cooperate with each other.

6:45 So you can fill squares that have come before if your opponent hasn't filled it.

6:49 Yes, obviously.

6:50 But some squares are going to be unoccupied at the end of the day.

6:54 All right, black's turn.

6:56 Black can't go there because of that red knight or there, but it can go there.

7:02 Red's turn.

7:03 Red plays here.

7:05 Black's turn.

7:06 Black it can't go here because it would be attacked by that red knight.

7:10 It's got to avoid any square that's being attacked by a red knight.

7:15 And we It's got to be the smallest unoccupied number.

7:18 So, I think it could go there.

7:21 There's no red knight within a knight's move of that square.

7:25 All right, it's red's turn.

7:27 Red continues from where it left off.

7:30 Seven.

7:30 Uh, seven is no good because of that.

7:32 Eight is no good because of that black knight.

7:34 10.

7:36 10 is free for red.

7:39 So now it's black's turn to play.

7:41 Can't go there because of that.

7:43 It can't go there.

7:45 It can No, it can't.

7:47 It can go there.

7:49 All right.

7:50 Black just played on square 15.

7:52 Red's turn.

7:53 Red can go here.

7:55 Black.

7:56 We left black at 15.

7:59 And we can put a black here.

8:03 Okay, red.

8:03 Back to red.

8:04 Here's red.

8:05 The last red was at 12.

8:07 We can't do 13.

8:08 We can't do 14.

8:10 15 is occupied.

8:11 We can do 24.

8:13 I think 24 can be red.

8:15 And it keeps going like that forever.

8:18 This is not a game that ends.

8:19 And it's not really a game.

8:20 The game, you could say it's a matter

8:22 of seeing um who can control the most territory.

8:26 But for the moment, we're just putting down knights and looking at the pattern.

8:30 And I am.

8:30 Yeah, you got me wondering that.

8:32 Yeah, obviously it's all predetermined,

8:34 but did playing first give you an advantage to have more territory or Yeah.

8:39 No,

8:40 in the end, no.

8:41 Didn't matter.

8:42 It evens out.

8:43 It It's pretty obvious it's going to even out in this kind of game.

8:47 There's no particular advantage.

8:48 And what you get, and this Jonas sent me a picture of this.

8:53 He he showed me what you get after a thousand squares.

8:57 I've indicated the starting square with a little

9:00 black circle and they alternate black.

9:02 It's this board but done for a thousand squares.

9:08 And you can see some strange things happened.

9:11 This bottom quadrant here is all red and it looks there's

9:16 an awful lot of black here and here it's all mixed.

9:20 So it's not clear what's going to happen.

9:22 That's a thousand a thousand squares.

9:25 And Jonas said it is totally unbelievable what happens.

9:30 This is for a 100,000 cells.

9:35 And you can see this is a a continuation of the first thousand cells.

9:44 This picture is a subset of this.

9:46 It's embedded.

9:46 It's in the middle.

9:47 You can see this chunk of red here has become a wide strip of reds.

9:52 In this strip, there are only red knights.

9:55 And then there's a strip of black knights.

9:58 And here you've got mixed.

9:59 So this little red corner you showed me is the start of this section here.

10:04 But it's only a strip.

10:07 Yeah.

10:06 And it's amazing that you would get this.

10:10 Where do these strips come from?

10:12 You'd think it would be totally random.

10:14 Yeah.

10:14 You had all this black.

10:15 You can still see the bits of white in there, too, though.

10:17 These are the blank squares.

10:18 The blank squares.

10:19 Yes.

10:20 Yeah.

10:20 Yeah.

10:20 How do these islands form?

10:22 What?

10:22 Yes.

10:23 Yes.

10:23 It's mysterious.

10:25 Yeah.

10:25 It's fantastic.

10:26 Did Did you catch that?

10:27 All right.

10:27 Let me show you the next stage in the evolution.

10:31 That was that was 100,000 cells.

10:34 When we get up to a million cells, it's fantastic.

10:41 Michael Branicki got involved at this point and he he contributed some drawings.

10:46 This is one of his.

10:47 There are my islands.

10:48 They're like,

10:49 "Yeah, they're the islands." And there are islands.

10:51 There they are.

10:53 And they stay there.

10:54 I mean, this this is a subset of this.

10:56 It gets it's the same picture, but just bigger.

10:59 This is a million squares.

11:01 As we go up, the red the black expands and gets more and more black.

11:06 By the time we get to 64 million,

11:09 black has totally taken over one quadrant of the board.

11:13 In fact, two quadrants separated by a strip which are kind of indecisive.

11:18 They can't really decide whether they're Republicans or Democrats

11:22 or in in terms of uh Stendal's novel where the red

11:27 represents the military and the black represents the church whether

11:31 they're going to be join the military or join the church.

11:35 solid black in two quadrants, two quarters of the whole infinite board,

11:41 or solid red in the top half.

11:44 Does this black and red now last forever or Yes.

11:46 Yes.

11:47 It just gets bigger and bigger.

11:51 Yeah.

11:50 Yeah.

11:50 They grow and the strips are thin strips and people

11:57 who are undecided whether they're going to be red or black.

12:01 And I don't know if this has any political implications,

12:05 but it certainly is astonishing.

12:08 It's very unexpected that it for so long it was making

12:12 patterns and then when it suddenly just said, "No, that's it.

12:15 That's it.

12:15 We're done." Yeah.

12:17 It's contagious.

12:18 You could say amazing.

12:22 Amazing.

12:22 Yeah.

12:33 Do you know what?

12:34 Has anyone done it with three colors now?

12:36 That would be interesting, wouldn't it?

12:38 Yeah.

12:40 Yeah.

12:39 Let's do it.

12:40 Let's do it now.

12:42 Should we do it?

12:43 No.

12:43 Because it'll take a long time to get enough colors for it.

12:46 It's going obviously going to be unsettled until the jelly sets.

12:50 Will it settle?

12:51 Will three colors settle?

12:53 Well, how will three colors settle?

12:55 because you haven't got those quad those obvious

12:57 quadrants like you do with a square board.

13:00 Like what will three colors do?

13:01 I'll investigate.

13:03 Giving you credit for suggesting it unless you want to work on it.

13:06 I I don't think I have the firepower.

13:08 We'll show you what happens with three pieces

13:10 in a bonus video over on number file 2.

13:13 We'll also show you what happens with more

13:15 pieces and pieces which move in different ways.

13:19 Trust me, it gets pretty crazy.

13:21 Check out the links below.

13:28 It gets stuck.

13:29 It cannot move.

13:30 Every square, every one of the eight squares around

13:33 it that it could move to, it's already been to.

13:36 So it d the sequence dies at that