Terrific Toothpick Patterns - Numberphile

we're at the kitchen table and we have toothpicks we put down one toothpick and we notice it has two ends so at each end we put a toothpick the toothpicks are all the same length ideally we started with one and we added two so now we've got three toothpicks we notice 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 we had for free ends we're gonna add four more toothpicks those those two toothpicks met at the middle so those ends are no longer free so now their word there are four ends so we add four more toothpicks now we've got eight free ends so we add eight to things 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 going to add eight and now we have 12 three ends we're going to add twelve two things and so on so let's watch it run we see it growing when we get to power of two we notice something special happens we have essentially a square that's full of toothpicks there's no room in the middle to 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 at 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 now the interesting thing is that the growth from the corners after 16 generations it's the same less the growth in the corners after 32 so let's let it run Freddie had my Harriet so we're coming up to a new power of two one hundred and twenty eight generations and again it's growing and it's growing from the corn it's hypnotic isn't that 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 from the corners is has the growth from the corners the corners grow like earlier corners grow and it grows and 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 see car 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 to fix now we've got four wingtips so we go there and they're there and let's let it run and swatch it admire it growing this is much more difficult we have not analyzed this here the growth from the corners is different at each power of two it's still every power of two it fills up a square as much as it can but the growth in the corners is much less predictable we even thought to make a double toothpick like Omar Omar Pole yes 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 as pretty as the picture but a different a different style II toothpick and see how that looks run yeah yes this is very Christmasy snowflake II and again we don't have to stand this at all we know how to generate it but we don't have a formula how many E's a toothpick star we go back to normal toothpicks now so here are ten 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 at the beginning one two three four we have eight free ends so we add eight and we get there and so on now in if we look at a corner and it's focus on a corner so after a power of two what we're left with is a square with no no holes in it it's full up and at each of the four corners there's half a toothpick sticking out the first step is all we can do is add one toothpicks there and we'd of course add one at the other four corners now the next generation this has two free ends so we add two toothpicks okay now we have three free ends so we add three more tooth which I'm now at generation what is it one two three we're gonna be able we've still got three free ends we add one two three and now we have one two three four free ends so we had four toothpicks 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 there if you go out to 128 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 at 256 but the beginning is the same always when you look at it you notice that after a power of two beyond where we were we have three clumps and so pay careful attention to how many there are we find as a formula and I was using L for the number in one of these clumps and here we've got three clumps two clumps which are seventh generational clumps and one which is eighths generation and we get a formula and when we actually put all the pieces together we find 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 one two three four five and so on there'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 there's there's a way of writing down how many toothpicks are are in the corner in terms of something we already know that's enough we can that we've now essentially cracked the whole problem we know every almost everything about it we have we can work out if you want to know the millionth term we can do it easily it solved a problem and we wrote a paper about it and well Paul 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 Alamos New Mexico Stanislaw ulam 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 its 0 or 1 maybe it's infected or it's not infected there's a disease spreading we want to know how fast the disease is spreading or maybe there's some chemical reaction which is going on it starts off with one cell being active and that activates other cell we want to know how fast does this grow it's it's it's understandable that this would be something that physicists and chemists and scientists and maybe nuclear scientists and mathematicians people are 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 Warburton cellular automata and it works on cells and it's a machine that's why it's called an automaton 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 we'll only look at the four nearest neighbors of the cell and we're going to start off where everything is clean the pristine board nothing is on suddenly one of the cells gets turned on I'll write a 1 instead of a 0 all the other cells are 0 the rule is for this particular automata 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 that like why is that's a zero and that's a zero but this cell here does get turned on because it's got only one neighbor that's on this is the ulema warburton cellular tourism so let's have a look at it no they can inversions of this of course Conway's Game of Life cells turn on and turn off these particular ones only turn on you either on or off and 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 ok next it turns on its four neighbors and next it turns on four neighbors again if did not turn on that one because the rule is you turn on if exactly one of your neighbors is on this one has two 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 callings and again we can analyze it in the same way and this one is even simpler there's a simple formula for how many cells are on after n generations now we've done the same thing but our graph paper isn't squared graph paper anymore it's 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 so watch if we let it run it 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 from 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 there's 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 of 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 here and then it grows and it grows and it grows and every you if we look here you can see this is sixteen so this is where we were after eight each power of two we we get a closed hexagon I'm just showing you one sector one sixths of the whole pizza just a slice so after sixteen 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 the 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 it and some of them are very beautiful I particularly wanted to show you Fred khun's replicator graduate students here at the University of Cambridge asked me if I could solve it and I did it was on the margin of what what could be solved and what couldn't but it was the rule is it's similar to the Olin Warburton you turn on if the number of neighbors that's on is odd not one as it was for that Warburton if it's two e's you turn off but an odd number you turn on yeah well the pictures are beautiful look at this here's the first 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 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 MIT studied many things like this mathematical things and so I found the game of life was sort of overshadowing much more important things and I did not like it we agree on that right two and 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

Channel: Numberphile

Views: 404,727

Rating: 4.9620695 out of 5

Keywords: numberphile, toothpicks, patterns, cellular autonoma

Id: _UtCli1SgjI

Length: 16min 6sec (966 seconds)

Published: Mon Dec 10 2018

Reddit Comments

[u/brianvaughn]

This was lovely.