Placeholder Image

Subtitles section Play video

  • We're at the kitchen table and we have toothpicks.

  • We put down one toothpick and we notice it has two ends.

  • So each end we put a toothpick, the toothpicks A ll the same length.

  • Ideally, we started with one, and we added two.

  • So now we've got three toothpicks we noticed.

  • Now there are four ends.

  • So on each end we put a toothpick and these toothpicks actually touch.

  • So those ends are no longer free.

  • And we keep going.

  • We do this forever.

  • So the next generation, this is the fourth step where we had four free ends.

  • We're gonna add four more toothpicks.

  • Those those two toothpicks met at the middle.

  • So those ends and no longer free.

  • So now they would therefore ends.

  • So we add four more toothpicks.

  • Now we've got eight Fri ends, so we add eight toothpicks and we keep going.

  • And the question is, how many toothpicks do we have after n generations?

  • Is there a formula?

  • Well, this is a very lovely question.

  • Let me show you David Applegate, my former colleague Bell Labs made an animation of this and a number of related sequences.

  • There we see one toothpick.

  • Next we added two toothpicks.

  • Next.

  • Next.

  • This is where we got to.

  • Now we're gonna add eight, and now we have 12.

  • Fri ends.

  • We're gonna add 12 toothpicks and so on.

  • So let's watch it run.

  • We see it growing when we get to power of two, we noticed something special happens.

  • We have essentially a square that's full of toothpicks.

  • There's no room in the middle toe.

  • Add any more toothpicks.

  • There's a horizontal line of toothpicks at the top in the bottom, and there are four free ends.

  • So by the rule that Step 17 we're gonna add four toothpicks.

  • The new toothpicks are always blue, so we've just added four.

  • And now if we keep going and you can see it growing from the corners, and the interesting thing is that the growth from the corners after 16 generations it's the same lets the growth in the corners after 32.

  • So let's let it run friendly and admire it.

  • So we're coming up to a new power of 228 generations, and again it's growing and it's growing from the corners.

  • Hypnotic, isn't it?

  • It's wonderful, yes, but you can do this on your on your computer at home and you can see it's growing, and it's obviously a fractal like structure.

  • The growth in the corners is has growth in the corners, Corners grow like earlier corners grew, and it grows and grows.

  • And the question is, how many toothpicks do we have after N generations?

  • And I'll show you in a minute how we analyze this, but there are others that we were not able to analyze.

  • So when you look at the sea eagle in the sky, it looks like that.

  • So that's actually a toothpick.

  • It happens to be bent, and it's got three ends.

  • The rule is the same.

  • Every free end, you add a toothpick.

  • Only this time they're going toothpicks.

  • Now we've got four wing tips, so we go there and they're there and let's let it runs.

  • Watch it.

  • Admire it.

  • Growing.

  • This is much more difficult.

  • We have not analyzed.

  • It's here.

  • The growth from the corners is different.

  • At each power of two, it's still every power of two.

  • It fills up on square as much as it can, but the growth and the corners is much less predictable.

  • You even thought to make a goal.

  • To think like that Omar Pole?

  • Yes, Her.

  • Isn't that wonderful?

  • Let me show you a couple of others before I show you a little bit of the mathematics of the analysis which is actually just a cz pretty as the picture, but a different a different style E toothpick and see how that looks.

  • Run.

  • Yeah, Yes, This is very Christmassy Snow, flaky and again we don't have to stand this at all.

  • We know how to generate it.

  • But we don't have a formula for how many ease e toothpicks.

  • We got back to normal toothpicks now.

  • So here are 10 generations and you notice that after eight generations we have a square which is almost full, as full as it can be.

  • There's no room to put a toothpick.

  • There are no free ends in the square.

  • There are only four free ends.

  • So after eight generations, we add four again.

  • It's just like in the beginning.

  • 1234 We have eight Fri ends.

  • We had eight and we get there and so on in.

  • If we look at a corner, let's focus on a corner.

  • So after a power of to what we're left with is square with no no holes in it.

  • It's full up.

  • And at each of the four corners, this half a toothpick sticking out.

  • The first step is, all we can do is add one toothpicks there.

  • And we'd of course, had one at the other four corners.

  • Now, the next generation, this has to free ends.

  • So we had to toothpicks.

  • Okay, now we have three fri ends.

  • So we had three more toothpick.

  • I'm now at generation.

  • What is it?

  • 123 We're gonna be able.

  • We've still got three Fri ends.

  • We add one, two, three.

  • And now we have 1234 free end.

  • So we had four to fix and so on.

  • After I think this is seven steps, it looks like that.

  • And if you stare at this, you see that it's really made up of three clumps the corner sequence after whatever it was.

  • Seven more steps.

  • And this is true for any power of two.

  • It's not just, you know that if you go out 228 steps, we still see the same growth.

  • 256.

  • It still starts the same.

  • It grows more and more because there's more room when we're out of 256.

  • But the beginning is the same.

  • Always when you look at it, you notice that after the power of two beyond where we were, we have three clumps and so pay careful attention to how many there are we find is a formula and I was using l for the number in one of these clumps.

  • And here we've got three clumps to clumps which air Seventh generational clumps and one which is eighth generation and we get a formula.

  • And when we actually put all the pieces together, we were in that we can explain the corner toothpicks.

  • I won't really go into the details, but there's a very nice formula which explains after we've gone for a power of two.

  • Plus I further steps where I is 12345 and so on.

  • That's a formula for the number in the corner, which depends on K, the power of two and I.

  • And it's a very nice recurrence.

  • Once we've noticed this recurrence that the number with this there's a way of writing down how many toothpicks there are in the corner in terms of something we already know.

  • That's enough weaken that we've now essentially cracked the whole problem.

  • We know almost everything about it we have.

  • We can work out.

  • If you want to know the millions term, we can do it easily.

  • It solves the problem.

  • And we wrote a paper about it.

  • No more poll David Applegate and myself.

  • So that one we solved in the end, you might say on the scale of things.

  • That was a pretty easy sequence to analyze.

  • Now there are a lot of others which are not so easy, like the Siegel toothpick and the E toothpick.

  • There is another couple of easy ones that I think are worth telling you about, particularly as they involve one of the famous scientists from Los Elements.

  • We makes Stanislaw Fulham.

  • Let's imagine we have a large piece of squared paper and each square is a cell, and we can say that cell is either alive or dead.

  • It's on or off it.

  • 01 Maybe it's infected where it's not infected.

  • There's a disease spreading.

  • We want to know how fast disease spreading.

  • Or maybe there's some chemical reaction, which is going on.

  • It starts off with one cell being active, and that activates other cells.

  • We want to know how fast is this crow?

  • It's understandable that this would be something that physicists and chemists and scientists and maybe nuclear scientists and mathematicians, people studying epidemics and so on.

  • This is of universal interest.

  • This question.

  • How fast does something spread?

  • A very simple version of this is what's called the alarm war Burton Cellular or Tom Merton.

  • And it works on cells and it's a machine.

  • That's why it's called an automotive.

  • It proceeds on its own.

  • And the idea is, we have to imagine we have a huge piece of graph paper with cells, square cells, and each one is surrounded by eight others, but actually will only look at the four nearest neighbors of the sale.

  • And we're gonna start off where everything is clean.

  • The pristine board.

  • Nothing is on.

  • Suddenly one of the cells gets turned on.

  • All right.

  • A one instead of a zero.

  • All the other cells a zero.

  • The rule is for this particular atomic.

  • You look at a cell near this, it gets turned on.

  • If exactly one of your neighbors is on.

  • This has one neighbor that's on so it gets turned on so that one turns on those four.

  • Okay, now let's go on at the next generation.

  • This cell here has two neighbors that are on, so it does not get turned on.

  • I'll put a zero.

  • Likewise, that zero and that zero.

  • But this cell here does get turned on because it's got only one neighbor, that's all.

  • This is the fool, Emma Warburton and sell your time.

  • So let's have a look at it.

  • No, they can.

  • In versions of this, of course, Conway's game of life cells Turn on and turn off these particular ones.

  • Only turn on.

  • You're either on or off.

  • Once you're on, you stay on.

  • And there it is.

  • It starts off with one cell on.

  • There it is.

  • It's blue because it's a new cell.

  • Okay, next it turns on its four neighbors.

  • Next, it turns on four neighbors again.

  • It did not turn on that one because the rule is you turn on.

  • If exactly one of your neighbors is on this one has to neighbors that are on so it stays off.

  • It is not infected.

  • If we let it run again, it's gonna grow up and again.

  • You'll notice that every power of two it's got a full square and it grows from the corners and again we can analyze it in the same way.

  • And this'll one is even simpler.

  • There's a simple formula for harmony.

  • Cells are on after N generations.

  • Now we're doing the same thing, but I graph paper isn't squared graph paper anymore.

  • It's a hexagonal Papers like the bathroom floors where you see hexagonal tiles.

  • This is hexagonal tiles.

  • Each cell has six neighbors now, but the rule is the same you turn on.

  • If one of you exactly one of your neighbors is on, it's a watch.

  • We let it run goes like this again.

  • It has the same property that after a power of two, we have a full hexagon and it grows from the corners.

  • But now something really annoying or beautiful has happened.

  • The growth in the corners were coming up to another power of two.

  • Here, watch it grow from the corners.

  • If you stare at this, you can see in here is a pattern of black and white cells at the next power of two, we see a different pattern.

  • It does not repeat.

  • It is very complicated.

  • And over there I have a very large piece of paper with my attempt to analyze it.

  • But you want to see it?

  • Yeah, course, Yeah, This is my attempt and it's not finished.

  • I haven't given up, but I haven't solved it yet.

  • This starts down here in the corner hair and then it grows and it grows and it grows.

  • And every you If we look here, you can see this is 16.

  • So this is where we were after eight each power of two.

  • We get a closed Mexican.

  • I'm just showing you one sector 16 of the whole pizza Justice slice.

  • So after 16 the we have that after 32.

  • It's like that.

  • And then if life was simple, there would be a predictable pattern.

  • But there isn't.

  • If you look at these squares, the colored squares, red squares, there are not like the red squares that we saw earlier.

  • There are some similarities, so I haven't given up.

  • But this is really tricky.

  • I think this one is doable, but some of the others and there are a lot as you saw there, there are 100 or more animations that you can look at and some of them very beautiful.

  • I particularly wanted to show you Fred Kins, Replicator graduate students and University of Cambridge asked me if I could solve it, and I did.

  • It was on the margin of what's what could be solved in what couldn't but it wa ce.

  • The rule is it's similar to the Alamo Burton you turn on.

  • If the number of neighbors that's on is odd, not one as it was for them or button, it's to ease.

  • Turn off an odd number you turn on and like, that's not here.

  • Well, the pictures of beautiful this here's the 1st 16 generations.

  • And then when you look at 32 generations, you ask, Can we break it up into pieces that look like things we've seen earlier?

  • And the answer is, Yes, you can, but it's a little tricky, okay?

  • And the reason it's called Friedkin's Replicator is if you have some shape, any shape you like, say that then after a certain number of generations, you see two copies of it.

  • It replicates itself.

  • That's why Friedkin being a famous computer scientist at M.

  • I.

  • T.

  • Who studied many things like this.

  • Lots of other mathematical things on dhe.

  • So I found the game of life was sort of over shadowing much more important things, and I did not like it.

  • We agree on that, right?

  • Two in three chance you've chosen a goat.

  • So this scenario, of course, should be of more interest to us.

  • It's the more likely scenario.

We're at the kitchen table and we have toothpicks.

Subtitles and vocabulary

Operation of videos Adjust the video here to display the subtitles

A2 toothpick grows power growth formula square

Terrific Toothpick Patterns - Numberphile

  • 1 0
    林宜悉 posted on 2020/03/27
Video vocabulary