Hydra game: An example of a counterintuitive mathematical result.

# What Is an Example of a Counterintuitive Mathematical Result?

The best answer to any question.
June 4 2014 10:55 AM

# What Is an Example of a Counterintuitive Mathematical Result?

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:

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:

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:

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.

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.

* * *