Placeholder Image

字幕表 動画を再生する

  • 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