I was recently introduced to the Hydra Game by the YouTube channel Numberphile (https://www.youtube.com/watch?v=prURA1i8Qj4).
In this video, they discuss many variants of the Hydra Game - cut off one head (i.e. a leaf of a graph, more specifically a finite rooted tree) and $n$ heads grow back. I am interested in the following variant (seen near the end of the video), also detailed on the Wikipedia page (https://en.wikipedia.org/wiki/Hydra_game):
You start with the Hydra being a straight line of vertices and edges, with a single root and a single leaf. At each step, call it $k$, you always pick the right-most leaf/head and chop it off, whereafter $k$ leaves will regrow from the grandparent of the leaf, to the right of any existing children. If you chop off a leaf with no grandfather, i.e. one level from the root, no leaves regrow (which is also why this game always terminates).
The challenge is to determine how many chops you need to cut off all the heads of the hydra. Both the YouTube video and the Wikipedia article lists the following result, for the hydra starting with $n$ edges: $n=1: 1$, $n=2: 3$, $n=3: 11$ and $n=4: 938038$. They also both state that the result for $n=5$ is unknown.
My question is, does anyone know anyone know a reference for this variant of the game, OR can someone spot the mistake in my code/approach?
I tried googling the Hydra game, and the number $938038$, but I only find the wikipedia page without any references, or articles discussing other variants of the game. The reason I am looking for a reference is that I seem to be misunderstanding this variation.
I feel that I am misunderstanding what "right-most" means. Since the grandparent of any leaf is always part of the original stem, i.e. one of the vertices that were there to begin with, and since no leaf can ever become a parent, it would seem to me that the "right-most" leaf is just the newest leaf on the level with most leaves. I wrote some simple Python code, which produces the correct results for $n=1,2,3$, but yields $327677$ for $n=4$ instead of $938038$. What am I doing wrong?
The code first sets up the hydra, with one vertex on each level (it forgets the root, since no heads can grow on this level). The first entry of hydra
is the upper-most level. It then loops while the final level still has heads, keeps track of how many chops have already been done, and for each chop, adds heads to the level below, except if the level is the final one.
def hydrachop(n):
hydra = [1 for i in range(n)]
step = 0
while hydra[n-1] > 0:
i = hydra.index(max(hydra))
hydra[i] -= 1
step += 1
if i < n-1:
hydra[i+1] += step
return step
EDIT: I reviewed my code using the comments, and wrote this:
def hydrachops(n):
hydra = [1 for i in range(n)] #hydra[0] is now one step from root
step = 0
while hydra[0] > 0:
for i in range(n):
if hydra[i] > 1:
break
if i<n-1:
if hydra[i+1] == 0:
break
hydra[i] -= 1
step += 1
if i > 0:
hydra[i-1] += step
print(hydra,i,step)
return step
This now outputs $1114111$, which is still wrong. If anyone has a modification to achieve $938038$, it would be much appreciated.
hydra[n-2]
to become $4$ (or more, but let's say it is $4$). The next move will be at level $n-2$, making it $3$ and increaseshydra[n-1]
by some amount. Next you must cut away all but one of the nodes at level $n-1$ before you cut the next head of level $n-2$. Note that the last move has level $n-1$ smaller than level $n-2$. Note also that you have to leave the one node which is part of the stem. You don't do it in this order, so the step count is off, giving smaller results. $\endgroup$hydra[i]>1
, but if there is no such index, take the lowest index for whichhydra[i]==1
. $\endgroup$