## Puzzle : Hercules and Hydra

Well, without any ado, let me directly dive into the problem at hand. This interesting problem was given to me by Ramprasad. As usual, he is the guy who brings in interesting problem with interesting solutions.

Problem : Most of you know the legendary battle between Hercules and Hydra. Please search on Wikipedia or Google to get the details of this mythological story. Anyways, let’s come back to mathematics. Let Hydra be a rooted tree.  As Hydra is a demon tree, instead of leaves, it has heads. And the internal nodes to which the heads are attached to are called throats.

Now, in the battle between Hercules and Hydra, Hercules can make a following move. At every move, Hercules can cut one of the head of Hydra.  At any i-th move, Hydra grows i copies of the throat from which the head was chopped off in i-th move. For example, if in 7-th move, a head is chopped off from throat T ( having 6 heads prior to chopping, and 5 after a head is chopped off ). There will be 7 copies of T ( with 5 heads ) as siblings to original T. Once all the heads from a throat is removed, the throat becomes a head.

1)      Argue that Hercules has a winning strategy for any finite Hydra. That is he can wipe out Hydra completely.

2)      Argue that any strategy employed by Hercules is a winning strategy for any finite Hydra.

Solution: Frankly speaking, I did not have any formal argument for the problems above. But I have an intuition that at every move, only the width of the hydra is increased and not the height.  Besides the copies of T generated, have one head less.

So, for any throat T with k heads at n-th move, let f(n,k) denotes the number of moves it takes to wipe out throat T along with all its copies. As long as f(n,k) is finite, we know that hydra can be wiped out. At any n-th move, we get copies of T with k-1 heads. However, now the n increases hence a simple induction does not go through.

Deepanjan came up with a proof for a special case of Hydra. Let Hydra have only one root node, only one throat attached to it, and m heads attached to this throat. Now, let us have an m-tuple (Hm,H(m-1), H(m-2),…H1) denoting the number of throats having m heads, m-1 heads and so on.

So initially, this tuple is (1,0,0,…0).  Before any move, if tuple is (a1,a2,…am) and after the move if it is (b1,b2,…bm) then we can state that (a1,a2,…am) > (b1,b2,…,bm). Where the order is defined as follows.

(a1,a2,…am) > (b1,b2,…,bm) if either a1 > b1 or a1 == b1 and a2 > b2 or a1 == b1 and a2==b2 and a3>b3 and so on. Hence, at every move, the value of the tuple is strictly decreasing. Therefore, after finitely many steps the configuration would be (0,0,…0) and the hydra is completely wiped out.

This can not be generalized to general hydra because number of heads can surpass m for some throat T. ( remember that when throat is reduced to a head, the inter node attached to it becomes a throat ).

From what I gather from Deepanjan, Ramprasad told that it uses trans-finite induction and Goodstein’s theorem. I am yet to meet Ramprasad in understanding the proof of these statements.

–Saurabh Joshi