The Hydra Game - Numberphile

You know you're dying to know we have no idea what we don't know, it's obviously a big number but we don't know the answer, we're going to play a

game

, the Hydra

game

, based on the Greek mythology of Hercules, the second labor of the 12 that Hercules had to complete to kill the lenan

hydra

had nine heads and every time Hercules cut off two of them they grew back and that is why this was considered challenging enough for Hercules and in a way he cheated because he liked to receive fire and burn the wound. so that the heads cannot grow back, but there is a mathematical way to solve this and calculate how many heads Hercules would have to cut off for this to end and that is that hydrogen will surely never end, you have to define the rules in the game of Hydra, the rules are potentially a little different than how The Legend of Hercules is told, but we can calculate how many heads Hercules cut off if the linear Hydra followed the mathematical rules of the Hydra, let's listen, listen, listen.

I'm ready, so the rules are: you have a root, so this is R, this is the beginning of your tree and it's what we call a rooted graph, which means there are some points coming out of your root and then you have some points , such a rooted graph just means that every point, every node, has a single parent that it comes from, that's about as simple as you'd expect, there are no inputs and outputs flowing, it's just a tracing of a single parent down to a path real at the bottom. and the way you play is you choose what we call a leaf, so stage one is to choose a leaf so this would be an X that we could choose and then also choose an integer n so an integer n and then delete that n is two in the Hercules example cut one out of two, grow back, remove X, so this is you've chosen, but now I need to add two new ones here, so I've cut off a head from my Hydra.

Two new ones grow, but they grow in a different position, that's how it differs slightly from the Legend of Hercules, but these are the rules of the Hydra game and then you go back and choose. a new sheet nine heads and Let's make it nice and symmetrical, so CU I think would have three types of main stems and then each of them has three heads, so it's been represented in many ways throughout history, but that's how it is . Definitely the way I've seen it represented is as a central body that is divided into three and then each of those three bits has three heads, so n is two and N is fixed, so every time we cut a head, it grows back from grandpa's grandpa yes exactly that's what you've already caught and that's really key to how this is going to work so again it's completely symmetrical is there any particular head you want cut?

Let's say your Hercules starts on the left. left or right, so we go to CH, so we choose our Sheet, our integer n is fixed, it's always two for Hercules, we have removed let's move on, so we cut this one again, two grow more, we cut this one from two more crops, so we will get a lot of heads and there will be another one where this Leaf node used to be and again we go. to cut another six every time we do it we get another two, so we're going to get another 12, right? So what we're left with is 1 2 3 4 5 6 7 8 n plus another 12 I added of those last ones, so we actually have 21 branches coming out of R, where R is this big root at the bottom, so that we ended up with 21 at the end.

How many have we cut so far? We cut nine, so we've taken nine steps so far, 21 left, but every time we cut one of these, there's no grandfather, we go back to the father, there's no grandfather, so it's like an implicit rule in how the game works , we can't go back any further, so no new heads grow. When we cut these, we are pruning exactly 21 plus the original nine we did, so the total for Hercules will be 30 heads. Hercules. actually has to cut, he can just cut those last 21 without exactly any growth and if we started here and then decided to cut one of these bottom ones, we would cut it, nothing would grow, but you still have another eight. leaving it like two levels deep, so I think the answer would be 30 for this example, regardless of the order in which you slice for this particular example, in other examples it will change, but here it's fine 30, so now we know how many Hercules has heads. has to cut is 30 if the real Lon, the real one, the mythical one and Hydra follows the rules of the Hydra gate, but a more general question we could ask is not necessarily how many steps until the game ends will the game end given a time specific.

Hydra in front of you, a specific graph, do we even know the game will ever end? Could there be an infinite number of steps? Because it feels like you're cutting one thing but adding more than one. We know that we will always get back on track and there will be nothing left, so that is the question that, as a mathematician, you are often interested in first: will it end? Before asking how many steps, let's investigate. Does the game ever end? I feel like it will always end, okay, that's a good intuition because the answer is yes, it will always end and the way we're actually going to do that is to pass it by induction.

You show that some of the first steps work and you show. that you can always continue increasing or decreasing from those first steps and you say, oh, so I repeat this forever and I'm fine with how it works, so we consider what we call the maximum distance between a leaf and a root, so the root is fixed, it's the bottom of the tree and the maximum distance in the Hercules example will be one, two, so we actually had nine points that were at a distance of two, but for Hercules D the maximum distance was two, the other stuff.

What we observed in the Hercules example was that once we were a distance away, that was all that was left, we could just cut them off and nothing new would grow, so once we get D equals 1, we're done, that's a fatal shot. Well, there might be four billion heads at that time, but we don't really care because there aren't any new ones coming. Mind you, if you're Hercules, you don't want to cut off 4 billion heads, but that's what you have to do. I have to do it, so once we get to D equals 1, we'll be fine, then the induction will be: can we find a way or argue why we can keep reducing d if we keep reducing it one by one?

It doesn't matter where it starts, eventually we have to hit one and we know it ends once we get to one, so if D is equal to 1, if D is greater than or equal to two, we are at a distance of two, there is some number of heads at that distance, so again for Hercules it was nine, but any graph where the farthest point at my original starting point again D was two but we only had two heads at that distance, there are a number of heads at that distance, let's call has the subscript D, so w is the number of heads and we are going to put the subscript D on it, which means it is the number of heads starting at a distance D, so we only do WD steps, so for Hercules we did nine steps, this one up here we do two steps we just remove all the heads on that level we don't care that this is necessarily the best or shortest way to solve it we just want to know that there is a way to solve this so it will end we can guarantee it will end so we just do that many steps and once the WD steps are done the new heads grow from the grandpa so every time you remove the distance D you get an amount because technically in each step you choose a new integer, not always is the same, which complicates things, but it doesn't matter, you add an amount to distance D minus one and that's the key, you can never add anything to distance D, you can never add anything to the level you are at, just you add the one below because you draw the line. from two down but it ends up being a distance one away from where you were so after WD moves forward whatever the number is now we only have D faces minus one remaining it could be a lot right this could be a really number big and each time If we do this, we could add 4000 heads each time or even billions of heads each time, so it could be an incredibly large number, but we only add heads at the bottom level, so now let's go back here and let's repeat exactly what we just did in D minus one we remove the small in a fixed finite number of steps and only add things at the D minus 2 level so now we are at D minus 2 again and every time we do this there will still be more numbers like grow but can't go to Infinity they can be big but actually can't completely flee to Infinity So over time it could take forever and we'll see some examples of that shortly but we'll get to D equals 1 and like you said that It's your kill shot, the

hydra

is dead, this feels like you've made some kind of formal, no, I know you haven't formalized it, but you've made a pretty elaborate test for something that just seems nice. from obvious to I'm glad you think it sounds obvious because often the things that feel obvious are the hardest to prove because you're starting from a point where this is obviously true like you said it yourself yes it will end I think it will end So It's very helpful to have that intuition and that kind of obvious aspect to you as a mathematician, but then formally writing down those steps is where you need training and practice as a mathematician, so I agree with you that it's probably overkill, but as a mathematician.

Generally speaking I'm pretty happy with this sketch of an induction, it could be a big number, but we can finish the game so we know it always ends, so now let's think about whether we can understand how big these numbers could be. just fix n to be a number like in the Hercules example. If it helps, think of it as two, but it could be any number instead of there being a potentially new number growing, let's fix it and see what happens there first. The step in induction was to remove all the heads at the WD level, so it will be the WD steps, so again in the Hercules example, WD was n, that was the farthest distance, there were nine now, how many have we added at the bottom level every time?

We did this and added n, so the next level started with WD minus one, which means the number at distance D minus one, but now we've added and many of the steps we've already completed below remove all the ones that started in WD less. 2 that's what the number at level D minus 2 means at the beginning, but now we've added n many of the ones we just did because every time we remove one at this level, it adds one to the previous level and this pattern is going to continue. So what is this actually? If you just simplify it a little bit, you get this n * that and then you get n^2 * the one two levels up so you can continue the pattern and eventually you'll get up to uh W would be D minus D minus1 would be W1 and then you'll have n from the previous level, but the previous level will be n many uh w d minus D minus 2 um and then you will get n 2 from the previous one, which I will write as W3 because it will be W1 W2 W3 and this goes up to n until D minus1 WD, this would be now take us to W1 and we know that we can finish from this point Kill Shot Turret, which is Killsh Shot territory.

There are a lot of heads in this level and now we have to remove them all, but we can finish in that many steps. so the total number of steps is the sum of all these total numbers of sword cuts, yes, the number of heads that have been removed. You want a visualization. This W1 only appears once, so it's W1 and then you have this W2. * n and here it would be a W2, so you get a 1 + n * W2 and then the pattern continues with a 1+ n + n 2 W3 plus dot dot dot plus 1 + n more until you reach n el^ of D minus 1 * WD because again WD is on all of these As you go up, that's what it represents, so this is a big number.

Now we can get an even better formula for this, so we can't tell you what the Ws are. That's just the number of heads at the beginning, but n is fixed, so given the amount you're adding, it grows back every time you're missing one of two for Hercules, um, because these things and this is a very good application of a geometric series, so a geometric series. is where going from one term to the next you multiply by the same thing so here you're just multiplying by n to get the next term there's a formula for that okay so if you have 1 + n + n^ 2 plus period point point to n the K a seriesgeometric is 1 - n k over 1 - n geometric series add up to K terms where this is the first second term, so when you enter this here what you see is the total number of steps for this simplified case is W1 plus now here we only have two terms, so this is 1 minus uh n^ 2 over 1 - n * W2 and then we get 1 - n Cub 1 - n * W 3 and then we continue with this last one is 1 - n la D over 1 - n w d this is the whole and the key here is that you have these powers of n increasing, so if n is like four and you have like 12 layers, this is 4 to the power of ^12, that's a very big number, it's exponential growth again, but like exponential growth, almost like on steroids, it's really like super super growth and this was for the simple case of n being fixed, so in the Hercules example, just to fully see how this works, D was two, we said that n It was fixed. at two W2 is nine nine at distance two and only three at distance one, so the total W1 is three plus we will only stop here for Hercules 1 - n^ 2, so it is 1 - 4 / 1 - n - 2, so it's Aus one at the bottom minus 3, which gives you three multiplied by 9, so it's 3 + three lots of 9, which is 3 + 27, which is 30.

Fortunately, my formula is correct, so this doesn't prove the formula, but we have derived it using geometric series and again that's for the simple case when n is fixed and we can already start to see how this is going to grow rapidly when n is potentially a number Pretty big, so we know it's growing quickly, but I can't emphasize how quickly and the best way to look at it is with what we call a rapid growth example. Actually, let's specify the rules here. We have to choose a leaf, so we're going to say: choose the rightmost leaf so that it doesn't have to be the farthest, so in our test and what we were talking about we were always looking further away and working backwards doesn't work here, it just says: pick the one furthest to the right, make it simple so it's like an algorithm to follow and the way your n is going to work the number grows back, so n is equal to the step in the which is found in step one one grows in step two the second head I'm cutting two grow back yes It's the third head I'm cutting when I started three grow back so the longer I let this work the worse it is for me like Hercules, so it's like you want to finish this as quickly as possible, so this is just one way.

It's like building in this kind of concept that n can also vary, so we just saw that M is fixed and you can understand that a little bit, but of course n is not fixed, so this is a way to allow n to change . and actually have it increase all the time, so this is where the growth will really explode. Yes, however, we know it will end because we had to prove that it will end, but how quickly does it end? Well, we'll look at the simplest possible graphs. We're going to look at straight connectors of length y, so if Y is one, you have your root and you have a single, that's length one, nothing more, so this one is easy, you go in and cut your head off, nothing can come back grow, it's dead, so that requires a total number of, let's call it steps, it's warm now if I have two straight lengths again, that's it, so again we're taking the simplest trees possible overhead rightmost, this was the first step, so a new one grows from the grandpa, I cut off the rightmost head, that's step two, but nothing can grow because it's on the bottom step three, we've lost it, so for this one , three steps so far, so good, not growing too fast and equals three, one, two, three, rightmost head.

You're going to have to help me follow the steps on this one, so that's step one, so I go back to my grandfather and one grows up. Step two, cut the head further to the right to grow because it was step two, cut the head further to the right, none of them grow so I've done three steps so far step four head further to the right nothing grows step five now it's up here now I need five down uh so that was step five now however there's six left at the bottom and when I cut them off Fortunately nothing new will grow so I think s will be 11 so we can see it's not there yet exploding, but you can see where it's going, so y is equal to 4 next on the right and this is the last one I'm going to draw. and I'm not actually going to follow the steps on this one because you know how many steps there are 98338 who, so I don't want to do that, feel free anyone who sees this is welcome to follow these rules in a simple and complete version. chain of 98338 steps omg to finish the hydro game but again it ends we know it has to end but it seems like a relatively simple set of rules the easiest possible chart we could have and yet almost a million steps and then y is equal to 5.

I know you're dying. to know, yes, we have no idea what we don't know, no one has been able to calculate it. Again we know it ends. We have proof that it must end, but we don't know how many steps are needed. I can not believe it. no one has done that looks like something that someone would have done with a supercomputer just for the fact that we don't know I don't know the answer Y is equal to 5 so challenge the spectator exercise for the spectator to I want to know I want that number, yes, like this what is that jump, it's true, is that jump from 11 to 983 thousand 000 is just crazy, this wouldn't be difficult to calculate, although it would be like if you just need a powerful computer like it's obviously simple, it feels like it should. be simple, but as someone who doesn't work in computational complexity, which is very much the field you're getting into, so no, I imagine the fact that it hasn't been done suggests it's not as simple as we .

I originally thought and I think this was the big clue that the jump is just that there's something else there, meaning something else is going on that makes this really complicated, but yeah, no, we don't know the answer for and equals 5, obviously that's a big number, but we don't know the answer awesome, great, if you liked this video, enjoy using your brain and even fancy the occasional monster, then watch today's brilliant episode, patronize their ever-growing collection of courses and quizzes covering a wide range of topics, mathematics, computing. science, just science in general, is incredibly interactive, as I hope you can see here, and it's made by people who really know what they're doing, smart, thoughtful people who also have a sense of humor, we watch what we eat, we exercise our bodies, why not learn? a daily habit to try shiny free for a full 30 days, visit the shiny.org snum archive or click the link in the video description and yes there is a QR code on the screen, if that's your thing sign up now and you'll also be able to get 20% off an annual premium subscription, which stops you, see, it's a jump of two each time, but then it resets at some point and I want to come back to this, so we'll see what 13 is real quick, so we don't restart there.

We affirm that we will not restart in the next one either. 14 will be 13