The Hydra Game - Numberphile

Tom Crawford is based at University of Oxford as Early Career Teaching and Outreach Fellow at St Edmund Hall and Public Engagement Lead at the Oxford University Department for Continuing Education.

NUMBERPHILE

Videos by Brady Haran. Animation by Pete McPartlan

[thedanielsturgeon]

Flash forward 11 months: ‘Hi, I’m Matt Parker, this is standupmaths, and today we’re calculating pi with the Hydra game.’

[Rubrickety]

Hercules should simply have dammed the water source. The monster would then eventually become dehydrated. Job done.

[PopeLando]

Long computation required? Better get Matt Parker to knock up some inefficient Python!

[ntecleo]

"obvious" and "trivial" are the words that haunted me throughout university

[AFastidiousCuber]

There's a version of this game where, instead of adding individual leaves, you add copies of the whole subtree. In this case, the length of the game grows so fast that proving it ends is independent of Peano arithmetic.

[Tekay]

The Comic "The Order Of The Stick" solved the problem on page 325 / 326. They just chopped of heads until the hydra has too many heads for its blood supply and passes out. You don't actually need to chop off all heads.

[EebstertheGreat]

It's interesting looking at how the myth of the Lernaean Hydra changed with time. At first, it just had six heads, and they didn't regrow. Later, it had nine heads, or just an unspecified multitude. The heads would grow back, either a single head replacing the old, or two, or sometimes three in the one's place. The way Heracles eventually defeated the Hydra changed as well. According to Apollodorus, his squire Iolaus cauterized each neck wound after Heracles severed the head, preventing it from regrowing. But according to later authors, he used the venom from the first neck wound to irreparably destroy the other heads.

[zakmaniscool]

the whole time I was watching this all I could think of was Danny DeVito shouting "Will you quit with the head-slicing thing?!?!"

[sbevecat]

Okay, some things I've figured out:
-The correct number of steps for n=4 is 1114111, not 983038. This number appears on an old blog and in wikipedia, so it probably was copied by some editor without checking and then by numberphile on this video.
-You can also calculate "equivalents". For example, for a [0, 0, 0] hydra, the equivalent would be a [0, 1] hydra starting on step 2. So, n=5 would be the same as a [0, 0, 0, 1] hydra starting on step 2. I can't calculate that yet, but I've calculated a [0, 0, 0, 0] hydra starting on step 2, and it is on the order of 10^6785212601122 steps. That number is still way, WAY smaller than the number of steps for n=5, which continues to grow a lot.

Maybe someone with more time or a mathematical background can make a formula to calculate these; I know it's possible for n<=2 (I used it to calculate the big number).

[AndyFletcherX]

Hercules was lucky that Tom Crawford didn't define his labours or he would have spent forever sharpening his sword.

[TomRocksMaths]

Send your drawings of the y=4 case to Dr Tom Crawford, St Edmund Hall, Oxford, UK.

[sternmg]

The sequence {1, 3, 11, 983038, …} for the simple linear starting graph _very roughly_ (in order of magnitude) grows like power towers of increasing height: {1, 2, 3^2, 4^(3^2), …}. If this holds, there could well be on order of 5^(4^(3^2)) steps for _n_ = 5, or _roughly_ 10^(183, 000) steps, give or take a factor of _n_ ( _in the exponent_ ). No wonder this number isn't known exactly!

[ksashi]

There's actually a game called Hydra Slayer that's all about chopping off these pesky hydra heads! And it also offers a nice mathematical puzzle, but not the same as the one described here - there's no "tree" of hydra heads, but instead you have a choice of weapons that chop off different amount of heads and cause different amounts to regrow, and you need to get the count to 0 exactly.

[collinmcclellan]

TLDR; for n=5 the number of steps is 2 * f^N (N) + 1 where f^N is f applied N times and f(x) = (x+2) * 2^x - 1 and N = 41 * 2^39.

We can think of the hydra problem as a process applied to an array of whole numbers, such as [1, 2, 3, 2, 2, …] for example, where there is also a step counter x. Each step removes the last number n and (if n > 1) appends x copies of n-1 to the list. I will denote f_L(x) as the value of the counter when the process has finished clearing a list L, if the process started at time x. First useful property: f_[a, b] (x) = f_[a] (f_[b] (x)). So we can decompose lists into a composition of functions. When k>1, f_[k] (x) = f_[k-1]^x (x+1) which is f_[k-1] applied x times at time x+1. Since any 1 will be removed in a single step, f_[1] (x) = x+1. We can now use the recursive formula to inductively prove that f_[2] (x) = 2x+1 and f_[3] (x) = (x+2) * 2^x - 1. We can check that this is correct by finding the known answers for n=1, 2, 3, 4.

n(1) = f_[1] (1) - 1 = 1
n(2) = f_[1, 2] (1) - 1 = 3
n(3) = f_[1, 2, 3] (1) - 1 = 11
n(4) = f_[1, 2, 3, 4] (1) - 1 = f_[1, 2, 3, 3] (2) - 1 = 17 * 2^16 - 1 = 1114111

Let’s find n(5) = f_[1, 2, 3, 4, 5] (1) - 1. We can simplify it to n(5) = 2 * f_[3, 4, 5] (1) + 1 since f_[1, 2] (x) - 1 = 2x+1. Setting N = 41 * 2^39, we can directly compute f_[5] (1) = f_[3, 3] (3) = N-1. Now, putting this together and using the recursive formula, we get n(5) = 2 * f_[3, 4] (N-1) + 1 = 2 * f_[3] (f_[3]^(N-1) ((N-1) + 1) + 1 = 2 * f_[3]^N (N) + 1 which is the simplest form I could get it down to. If we make the approximation f_[3] (x) = 2^x, we get a lower bound of 2 * 2^2^…^2^2^N + 1 where the power tower has height N. It’s really big. Please let me know if you find any mistakes I’ve made!

[NzOrangutan]

Just chopping off all heads generated by chopping the highest level head in the 5-level Hydra (following the rule of always chopping off the most recently generated lowest head) is removing a total of 21, 990, 232, 555, 519 heads (i think). Therefore Chopping the one remaining new highest level head (original 4th level head) generates 21, 990, 232, 555, 520 heads at level 3. Chopping one of these will generate 21, 990, 232, 555, 521 heads at level 2. All told, removing these lvl 2 heads (in the correct sequence) will generate (21, 990, 232, 555, 522 + 1)*(2^(21, 990, 232, 555, 521)-1) - 21, 990, 232, 555, 521 heads at level 1 (directly connected to root, generates no more heads) to be removed before the next of the 2E13 remaining level 3 heads is removed (i think).

[xtieburn]

This reminds me of the TREE sequence that goes TREE[1] = 1, TREE[2] = 3, TREE[3] = Is a number so absurdly large one of the only things we know about it is that it far exceeds the size of Grahams number.
(and I believe numberphile has some videos on the TREE sequence already.)

[miroslavhoudek]

The true solution to the Hydra game is to join Hydra. Hail Hydra.

[marasmusine]

"You enter a 20' by 80' room. A long oak table runs down the center surrounded by chairs. Sunlight filters in through windows on the west wall. The north and east wall are lined with bookshelves laden with old tomes. Some are kept imprisoned behind brass grills, as though yearning for escape."

[magusofthebargain]

Assuming that the mythical hydra doesn't follow the rules of your hydra game, and there is a never ending supply of 2 heads that grow for each head chopped off, my answer would be to fight the hydra in a cave with the cave opening being smaller than the cave itself. Eventually, the hydra would grow so many heads that it would be trapped inside the cave, unable to squeeze its way out. Even if it gnaws off one of its heads, two grow back, right? Alternatively, if conservation of mass is considered, and heads grow back smaller and smaller (like Jake stretching too far in that one Adventure Time episode, even if the Hydra escapes the cave, each head would eventually be so small that the bite would be ineffective, and the beast with thousands of tiny heads would be easily defeated before it could escape the cave and grow larger.

[uzqap]

Always cutting off one of the longest heads on the single line hydra should result in the fewest cuts. With the regrowth from 16:27 a recursive function can be formulated:
f(x)=x+(f(x-1)^2+f(x-1))/2
f(3)=9
f(4)=49
f(5)=1230
f(6)=757071