Hercules Versus the Hydra is a Greek legend about Hercules fighting a monster called the Hydra. According to Greek mythology, the Hydra - often known as the Lernean Hydra - was a monster with many heads who lived in a marsh near the region of Lerna. Every time Hercules chops off one of the Hydra's heads, multiple new heads grow back. Whether or not Hercules will win the battle and destroy all the heads of the Hydra will depend upon how many heads grow back each time one is removed.
We start with a string of the letters 'a' and 'b'. The aim is to destroy the string, with three rules: each turn, the first letter is lopped off, an 'a' becomes 'ab' and 'b' stays the same.
a → ab
b → b
This work explored the range of possible outcomes under different rules, and starting strings. Examples of games under the simple case (two letters and three aforementioned rules) are shown below. The first is a short game, starting with the string 'abb' the second is still a fairly short starting string, 'abaaba', but with many more steps.
The initial observations of this simple game are listed below. The game gets more interesting when we introduce more letters and rules. Check out the report.
Hercules will always win:the 'a' closest to the left of the string will always eventually become the first entry, and will be lopped off, this may take very many steps though.
The minimum number of steps for a string of length 'n' will be n:this will happen for a string consisting only of 'b's since they do not increase the length at all.
The maximum number of steps for a string of length 'n' will be 2ⁿ − 1:this will happen for a string of 'a's, see report for full explanation and proof.
You can read the full report here.