As mentioned in the riddle description, this is a classic one. As such, it has
a one-line, elegant solution. It appears towards the bottom of this page.
What the elegant solution is not, however, is elementary. In fact, for reasons
that will also be explained later on, I've heard from many people an educated
explanation as to why this riddle *has no* elementary solution.

Using your Head is Permitted takes the stance that there is no such thing as a mathematical question without an elementary solution (although this solution may be exceedingly complex and unintuitive -- granted). You will be the judge of how good the elementary solution described here is.

Now consider what happens when Hercules chops off a head. Clearly, if we
replace any sub-tree within the Hydra with a sub-tree of smaller value, the
entire value of the tree will decrease. The sub-tree that actually changes in
each round of the melee is a neck piece (not severed) connected to a neck
piece (severed) and some additional sub-tree (whose value we shall denote
*x*). The total value of the removed part is therefore
4^{x+1}. After severing, this is replaced by 3 copies of
a sub-tree whose value is 4^{x}, for a total of
3*4^{x}<4*4^{x}=4^{x+1}.

The total value always decreases and so, because the naturals are well-ordered, the fight must ultimately end (despite being perhaps very long).

The surprising solution is therefore that Hercules always wins against the Hydra, regardless of his strategy or the Hydra's strategy.

Unfortunately, in Part 2 the number of copies heads get multiplied by grows all the time, with no limit. Ultimately, it will cover all the naturals.

The elegant (but not elementary) classroom solution for Part 2, is simply to
take as a representation base something that is larger than all naturals:
*ω*, the first non-finite ordinal. Readers fluent in ordinals will
have no trouble recognizing that when doing so, the total Hydra value is,
itself, an ordinal (and not a very large one: its cardinality is
ℵ_{0}
regardless of the shape of the Hydra). As in Part 1, any move by Hercules is
bound to decrease the ordinal value, and because ordinals are well-ordered
(this being the truly non-trivial part), the battle is guaranteed to be won,
regardless of the strategies used by either Hercules or the Hydra.

Readers who have read last month's riddle may see already where the elementary solution is going to come from: suppose that we use as the value of the Hydra its tree's Euler number. It is trivial to ascertain that this value decreases with each swing of Hercules's sword (details left to the reader), and, as proved last month, Euler numbers for trees form a well-ordered set, so the battle is guaranteed to eventually be won by Hercules.

Another item that I am leaving to the spirited reader is to show that the ordering of the Euler numbers and the ordering of the ordinals are one and the same. Ordinals, in other words, are not a magical ingredient in this solution. Rather, their function can be emulated through elementary means.

(Having said that, this would be the appropriate time to mention that several
readers tried to answer last month's riddle by various attempts at an inductive
argument on trees. The reasoning [made here somewhat simplistic and obviously
falsifiable -- it was far more crafty in the actual solution attempts]
was basically as follows. "Let us denote a
subset of the trees *S* to be a set regarding which we know that it is
well-ordered. We begin with *S* being empty. Now, let us pick the tree
*t*
with the smallest Euler number which is not in *S*. Clearly, any sequence
of trees with descending Euler numbers which passes through *t* must be
finite: the next tree after *t* must be in *S*, for which we know
that all descending sequences in it are finite. Ergo, we can add *t* to
*S*. By induction, Euler numbers for trees are well ordered."
The problem with this argument is that the topology of trees is not like the
topology of natural numbers. Rather, it is like the topology of (small)
ordinals. As such, standard induction does not work. If you want to use
induction on trees, you need to develop the equivalent of transfinite
induction, which is what works on ordinals, and this is easier to do on the
ordinals themselves, rather than on trees. Any use of induction in this riddle
must be carefully planned so as to only induct on naturals, such as the tree
height or the number of leaves, never on the trees themselves.)

While on the topic of completing items from last month's riddle, I promised last month that I will return to the August riddle with an elegant solution. The elegant solution is simply the reverse of the present solution: "Because the order of Euler values is the same as the order of the ordinals associated with the same tree, the well-ordering property of ordinals is shared by the Euler values. Q.E.D."

Some words about the history of this problem, and why people sometimes believe
that it has no elementary solution:

In 1944, Reuben L. Goodstein described what is now known as
"Goodstein Sequences".
You can read about these in Wikipedia, but the basic idea is to describe
numbers in base *b* such that all coefficients are also in base *b*,
recursively (otherwise known as *pure base* representation or
*hereditary* base-*b* notation). We
now iteratively replace all *b*s in the representation by *b*+1's,
subtract 1 from the result, represent the new result in pure base *b*+1,
and repeat. This process was hinted at in the riddle itself, by the mention
of 2^{3} and 3^{4}.

The result is a sequence of values that increase astoundingly rapidly. However, Goodstein managed to prove, by replacing the basis with an ordinal, that ultimately, the numbers will fall back to zero.

More astoundingly, in 1982 Laurie Paris and Jeff Kirby showed that
Goodstein's theorem is *not provable* in ordinary Peano arithmetic.
They reinterpreted the construction of Goodstein's sequences in terms of
the Hydra game described in the riddle. (Astute readers will notice the
similarities. Basically, Goodstein's sequences are what you get if you try to
apply the Part 1 solution for Part 2, and just keep bumping up the base of
representation so as to make sure that in the new base of representation
Hercules's actions have a positive impact.)

These two riddles, whether Goodstein's sequences terminate in zero and whether Hercules defeats the Hydra, are both examples for "natural" questions that cannot be solved within Peano arithmetic. It is this statement that is sometimes misconstrued to mean that the problems have no elementary solution, or that ordinals must be used. However, as demonstrated in the last two months, the tree construction itself is already a step beyond Peano arithmetic, and nothing non-elementary really needs to be added in order to present a solution to the problem.