The Graceful Tree Problem – Numberphile


What’s this, Brady? It’s like a graph, or joined up circles? No, this is an ant. You can see the antenna up there, and then this is the body of the ant. Oh yeah, OK. We’re going to place odd consecutive integers starting with one into this ant. So, what are those odd consecutive integers starting with one? Well, we need one, three, five, seven, and nine. We’re going to be placing them in here. So, what number do you want here? Seven. Seven, and here? Three. And here? One. Let’s put nine. And? Five. OK, so this is an example of a failure. We’re going to look at five minus one; that is four. 4 9 minus 1 that’s 8 3 minus 1 that’s 2 everything looks different so far looking good Sadly 7 minus 3 is also 4 so we failed this is an example of a failure your job, is to try to make all of those differences different if I go seven three one nine five then we have 4 & 8 & 6 & 4. Oh wait no this is still a disaster I wonder if this is even possible to solve this at your you’re okay to fail but I I’m supposed to be succeeding here okay um let’s go 9 1 No, maybe I’m gonna put the 7 up Here and the 5 here and a 3 here does this work Yeah yeah yeah yeah this looks good so this is nine minus one that’s eight seven minus one six four and two We’re all different we are successful we get to ride the end So this is part of an unsolved problem from 1967 called the graceful tree conjecture but it belongs in every elementary school’s curriculum, whenever they’re learning subtraction so the general problem is given any number of connected circles so they have to be connected any number that you want they have to be connected and there can be no loops so this would be a fine Insectoid to solve let me show you a loop so you could ask can this be solved so this might be solvable it might not But it’s certainly not the graceful tree conjecture the graceful tree conjecture means that there’s no loops, okay? okay, but why don’t we try to solve this so now we need 1 3 5 7 & 9 in 2 & 2 here can this be solved Consider how many even numbers you can get what’s the biggest even number that you can get as a difference between these right 8 yeah 9 and 1 the biggest you can get is 8 what’s the second biggest number that you can get 6 yes and The third biggest number 4 and then the last one is 2 there are only 4 different numbers that you can have but how many lines do we have to satisfy we have got 5 lines we’ve only got 4 even numbers to distribute between these five lines So no matter how you distribute these odd numbers You are always going to end up with a duplicate so here we have 8 6 4 2 & 4 again We’ve ended up with a duplicate over here so this starfish Cannot be solved it will fail every time if we have n circles and n lines connecting them We will never be able to solve that we can potentially solve for M circles in this case 5 circles and n minus 1 Maximum of four lines, we? Sometimes can solve for that so five circles where you you could solve it so here’s a butterfly There are five lines and one less connector so this could be solved what about this Five circles and four connectors I don’t know if this can be solved but this might be able to be solved the graceful tree Conjecture doesn’t include loops but this is still an Interesting question I I don’t know the solution to this so the graceful tree conjecture is one where you have all of your circles connected So you don’t have an outlier here and there’s no loops So that is guaranteed if you’ve got n circles you’re going to have n minus 1 connectors so here we’ve got 1 2 3 4 5 6 7 circles 1 2 3 4 5 6 lines and this is what is unsolved whether 4 n circles and n minus 1 lines Where there are no loops Can you always put in there odd? consecutive integers such that the difference between all connected circles all of those differences Are different what’s it’s not proven for that surely you mean for old designs of three oh yeah for all insectoids or all trees that you would care to design so this one for seven has been solved this is an example of Seven circles and six connecting lines there are actually 11 different ways that you can do that so here we have the 11 different ways to have seven circles all connected no loops What is unsolved is? going for more circles if you go into 30 or 40 circles Are these all solvable this has been an open conjecture since 1967 so presumably God if I start having more circles like 30 circles of 40 per calls the number of insectoids possible must just get metal it explodes Exactly right up to what number of circles is it solved for there are individual cases that have been solved for example I can put Circle in the middle and I can add any number of Circles on the outside that you want and this is always solvable and I can prove that quite easily I can put a 1 in the middle then I can go 3 5 7 9 11 13 15 17 19 21 23 And you can imagine I can keep on going here and this is always solvable because these differences are always different I could also put The largest number in the middle 23 could go in the middle and then I could distribute The other numbers all around all we solvable another example of a species that is always solvable are Snakes so you could imagine a snake of any length that you want and these are always solvable you might want to try this you can start with one and then you can go to your largest one I’m actually going to just skip I’m gonna go 1 3 5 7 and then I’m gonna come back 9 11 13 here, we have a difference of 12 a difference of 10 a difference of 8 a difference of 6 a difference of 4 and a difference of 2 All snakes can be solvable just by replicating that pattern there’s lots of species out there Not everything is a snake not everything is a sea star There’s lots of species out there you could very easily create and explore new species for example what happens if we have Something crazy that you know to sea stars joined with the long dendritic chain So is that solvable you can imagine that these can get very very complex very very quickly and Most species by the time you get to 40 circles most of those insectoids Very difficult to solve so presumably good if this is still an unanswered question That means there’s yet to be a species of tree found that is definitely Unsolvable because that would that would ruin it that’s correct We have not found an example that doesn’t work but that doesn’t mean that it doesn’t exist there are plenty of mathematicians who believe that that tree Exists that that there is a tree out there that cannot be solved would you be happy or sad if one was found oh I would be thrilled if one was find because I do this with my elementary school kids and after a week of them struggling to find one that can’t be solved I would love to say and Here, we have but it feels like it feels like nature is telling us they can always be solved like it feels like a Beautiful thing they’re also about it feels like it would break something beautiful Well it’s already broken like if you look beyond the graceful tree conjecture to allowing loops so here we have seven circles Six connectors so these ones cannot be solved so in a way it’s already broken but it’s interesting which Species work which species fail I like that I sort of see them as abominations and therefore they should It’s fair enough that they can’t be solved but there’s something perfect about the tree that has no loops and no islands Well that that’s where the crux is well where does a dividing line between Species that are always solvable and species that aren’t that’s what becomes interesting Are, you right are all of the trees really beautiful, well we’ll have to wait and find out

100 Comments

Add a Comment

Your email address will not be published. Required fields are marked *