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 4x+1. After severing, this is replaced by 3 copies of a sub-tree whose value is 4x, for a total of 3*4x<4*4x=4x+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 bs 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 23 and 34.
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.