The Hydra Problem

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 here, if you are wondering what the mysterious symbol ωω means, check out the ordinal numbers at Wikipedia).

However, you want to show only that Herculescan 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 naturalnumber), so finally Hercules will manage to cut all the heads of the bottom-most level. the root is at the top (as in the diagram you supplied) and consider the lowest level of the tree.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s