This question originally appeared on Quora.
Answer by Michal Forišek, computer science lecturer at Comenius University:
The Hydra game!
Imagine that you are Hercules, and you were given the task to slay the Hydra. Here is one possible hydra:
Courtesy of Michal Forišek
Our hydra is a rooted tree. The root (black, at the bottom) is the body, and the leaves (blue) are its heads. Just like Hercules, you are going to cut off its heads, one at a time. But, just like with the mythical Hydra, each time you cut off one head, it may grow some more in other places. Here’s the rule:
You can cut off a head that is connected directly to the root. In that case, nothing grows back. In all other cases, you grow new heads as follows:
- Let x be the vertex where the head you just cut off was attached to the Hydra.
- Go down one edge from x, let y be the new vertex.
- Grow two new copies of the entire subtree you just came from. (We will call this the growth rule.)
A picture is better than words, so here’s what happens when you cut off one head of our Hydra. Below, the head we decided to cut off is now dashed, and we show the vertices x and y:
Courtesy of Michal Forišek
And now we take the subtree we just came from (vertex x and two leaves) and we add two new copies of that subtree at y:
Courtesy of Michal Forišek
We just cut off one head and got four new heads in return. Not good. Let’s try that one more time, this time cutting off the second head from the bottom.
Courtesy of Michal Forišek
Now we have 19 heads. Looks like this Hydra will be pretty tough to kill. You can kill the head at the bottom to go down to 18, but then any next kill will increase the number of heads again.
At this moment your intuition probably tells you that killing a Hydra is a hard job. Sure, some tiny Hydras can be killed—if you have just a body and a few heads, you cut off the heads, and that’s it. But if you try killing any nontrivial Hydra, after the first few cuts, your situation will look like in our example. Don’t just take my word for it: Try it yourself.
Now, it wouldn’t be too surprising if I told you that you can always win the Hydra game. Instead, I’ll tell you something you certainly don’t expect: You cannot ever lose the Hydra game. You will always kill the Hydra in finitely many turns, regardless of how large the Hydra is, and in which order you kill the heads.
And it gets better. Let’s make the game harder. See the word two in the growth rule? Let’s change it to 47. Even with 47 new copies of a subtree added in each turn, you still cannot lose the game.
Let’s now change the growth rule as follows: If this is turn N of the game, grow N new copies of the entire subtree you just came from. That is, the longer you play, the faster the Hydra grows. You still cannot lose the game. Regardless of how you play, the Hydra is still guaranteed to die in finitely many steps.
Here’s the most awesome version of the growth rule: Pick any positive integer N. Go ahead, make it as large as you wish. You can even pick a different N each time, and make each choice greater than the previous one. Grow N new copies of the entire subtree you just came from.
Guess what? You still cannot lose. Each possible game still has to be finite. There is no way to make an infinite sequence of valid moves.
* * *
Here’s a sketch of the proof: We can assign an ordinal to each possible hydra using a recursive formula: A single node gets the ordinal 0, and α node with children α1 through αk (sorted in decreasing order of assigned ordinals) gets the ordinal ωα1 + … + ωαk, where αi is the ordinal assigned to the tree rooted at αi. It can now be shown that every valid move decreases the ordinal assigned to the hydra. And as there is no infinite decreasing sequence of ordinals, every possible game must be finite.
If you just got lost and scared, here’s a bit of intuition behind what’s going on in the proof. We basically say that whenever something goes on K steps away from the root, it’s infinitely times worse than anything that is going on K-1 steps away from the root. Now, whenever you kill a head, you very slightly simplified something that is K steps away. And even though you get a lot of new stuff in return, all that stuff is only K-1 steps away, and hence the entire result is still simpler than it was before. (That’s as good a description as I can give in one paragraph.)
And to top it all off: You may now ask for a simpler proof. You won’t get one. Proving that the hydra game is finite is hard. In particular, in 1982 Kirby and Paris proved the following theorem: “Any proof technique that proves that the hydra game is always finite must be strong enough to prove that Peano arithmetic is consistent.”
More questions on Quora:
