Fight against the Hydra - Graph Theory

Question

The following problem is supposed to be a nice application of the basic knowledge of graph theory. I consider it however as difficult and I would be happy if someone could help me find a solution.

Let's consider the Hydra (creature of the greek mythology) :

We can compare it to a tree quite easily: $T = (V,E)$

-The tree has root $r \in V$. The root corresponds to its torso and the leaves of the tree correspond to its heads.

-$p(v)$ gives us the parent node of a node $v \in V − \{r\}$ in the tree.

-If Hercules cuts a head $\ell \in V$ (so that $p(\ell) \neq r$) of the Hydra, it will grow back according to the following rule:

let $T_\ell$ be the subtree with the root $p(\ell)$ after the leaf $\ell$ has been removed (cut in our case), we just add two copies of $T_\ell$ to $p(p(\ell))$.

-The Hydra is considered as defeated when there is just the torso left.

Now the question:

Is it possible for Hercules to kill EACH Hydra?

Answer 1

The nice thing about the hydra game is that Hercules cannot lose. Whatever he does, as long as he keeps cutting the heads, he will kill the hydra (but perhaps after a loooong time). The proof is not complex, but requires a bit more sophisticated machinery than basic graph theory (it is nicely summed up in the article pointed out by @anorton, i.e. here, if you are wondering what the mysterious symbol $\omega$ means, check out the ordinal numbers at Wikipedia).

However, you want to show only that Hercules can kill any hydra, not that any strategy will kill any hydra. The former is much weaker statement and there is a basic proof of that.

Hints:

1. The height of the hydra tree cannot increase.
2. Make Hercules cut off any head that is as far from the root as possible.
3. Hercules can decrease the height of the hydra tree.
4. Use induction on the tree height to show that for any hydra Hercules can kill it.

If the third step is too hard, find a more detailed explanation below:

Assume the root is at the top (as in the diagram you supplied) and consider the lowest level of the tree. Group the leaves by the parent, e.g. tree $\Big(\big({\bullet}{\bullet}\big)\big(({\bullet}{\bullet}{\bullet})({\bullet}{\bullet})\big)\Big)$ would give you $({\bullet}{\bullet}{\bullet})({\bullet}{\bullet})$ or $(3,2)$ for short (the first two leaves were not taken into account because they do not belong to the lowest level). Now assign a number $4^3 + 4^2$ to it, or in general $4^{a_1} + 4^{a_2} + 4^{a_3}+\ldots$ for $(a_1, a_2, a_3, \ldots)$. Observe that when Hercules cuts any of the heads, the exponent decreases and we get two new copies. To give an example, if Hercules had cut a head in the first group, we get \begin{align}3\cdot4^{a_1-1}+4^{a_2} + 4^{a_3} + \ldots < 4^{a_1}+4^{a_2} + 4^{a_3} + \ldots \end{align} which means that the natural number we assigned decreases. It cannot decrease forever (it is a natural number), so finally Hercules will manage to cut all the heads of the bottom-most level.

I hope this helps $\ddot\smile$