This is the prior post with the answer to hydra(5). In this post, we’ll be providing the exact sequence for the general hydra problem.
Also wikipedia page: https://en.wikipedia.org/wiki/Hydra_game
See the previous post for an explanation of how the game is played, and the notation I’m using:
([a, b, c, d, e, …, n], S)
Feel free to scroll down to the solution if the proof isn’t of interest.
(a)\ ([1], S) \rightarrow S;\ \text{on the S-th step, the last head is chopped}
(b)\ ([1 + a, \ldots], S) \rightarrow ([1, \ldots], S + a)
Starting with b = 1:
(c)\ ([1, 1+1, \ldots], S) \rightarrow ([1 + S, 1, \ldots], S + 1) \to ([1, 1, \ldots], 2 \cdot (S + 1) - 1)
Let’s define the function that decrements the 2nd index by 1 as B(x):
And generally define the n-th nesting of any function to be:
F^n(x) = \underbrace{F(F(\cdots F}_{n\, \text{times}}(x)\cdots))
Continuing with B = 2:
(d)\ ([1, 1+2, \ldots], S) \rightarrow ([1 + S, 1 + 1, \ldots], S + 1) \to ([1, 1 + 1, \ldots], 2 \cdot (S + 1) - 1)
(d, cont) \to ([1, 1, \ldots], 2 \cdot (2 \cdot(S + 1) - 1 + 1) - 1) \to ([1, 1, \ldots], 4 \cdot (S + 1) - 1)
Noticing the same trend as b = 1, generalizing the function B:
(e)\ ([1, 1+b, \ldots], S) \to ([1, 1, \ldots], 2^b \cdot (S + 1) - 1)
and if … is all 0’s, then:
(f)\ ([1, b], S) \to ([1], 2^{b} \cdot (S + 1) - 1) \to 2^{b}\cdot(S+1) - 1, \text{per (a) & (e)}
Quick sanity check, hydra(2) = 3, which this formula conforms to.
Generally:
2^{b}\cdot(S+1) - 1 = B^b(S)
Starting with c = 1:
(g)\ ([1, 1, 1+1, \ldots], S) \rightarrow ([1, 1 + S, 1, \ldots], S + 1) \to ([1, 1, 1, \ldots], 2^S \cdot (S + 2) - 1 = B^S(S + 1))
Let’s define a function C(x):
C(x) = B^x(x+1) = 2^S\cdot(S+2) - 1
(g, rewritten)\ ([1, 1, 1+1, \ldots], S) \to C(S)
with c = 2:
(h)\ ([1, 1, 1+2, \ldots], S) \to ([1, 1 + S, 1 + 1, \ldots], S + 1) \to ([1, 1, 1 + 1, \ldots], C(S)) \to ([1, 1, 1, \ldots], C^2(S))
generalizing…
(i)\ ([1, 1, 1+c, \ldots], S) \to ([1, 1 + S, 1 + c - 1, \ldots], S + 1) \to ([1, 1, 1 + c - 1, \ldots], C(S)) \to ([1, 1, 1, \ldots], C^c(S))
if … were 0’s:
(j)\ ([1, 1, c], S) \to ([1, 1 + S, c - 1], S + 1) \to ([1, 1, c - 1], C(S)) \to ([1, 1, 0], C^c(S))
(j, cont) \to ([1, 0, 0], B(C^c(S))) \to B(C^c(S))
Quick sanity check for hydra(3) = 11:
([1, 1, 1], 1) \to B(C(1)) = 2 \cdot (C(1) + 1) - 1 = 2 \cdot (2^1 \cdot (1 + 2) - 1) + 1) - 1 = 11
Starting with d = 1:
(k)\ ([1, 1, 1, 1+1, \ldots], S) \to ([1, 1, 1 + S, 1, \ldots], S + 1) \to ([1, 1, 1, 1, \ldots], C^S(S+1))
Let’s define a function D(x):
(k, rewritten)\ ([1, 1, 1, 1+1, \ldots], S) \to D(S)
with d = 2:
(l)\ ([1, 1, 1, 1+2, \ldots], S) \to ([1, 1, 1 + S, 1 + 1, \ldots], S + 1) \to ([1, 1, 1, 1 + 1, \ldots], D(S)) \to ([1, 1, 1, \ldots], D^2(S))
generalizing…
(m)\ ([1, 1, 1, 1+d, \ldots], S) \to ([1, 1, 1 + S, 1 + d - 1, \ldots], S + 1) \to ([1, 1, 1, 1 + d - 1, \ldots], C(S)) \to ([1, 1, 1, \ldots], D^d(S))
if … were 0’s:
(n)\ ([1, 1, 1, d], S) \to ([1, 1, 1 + S, d - 1], S + 1) \to ([1, 1, d - 1], D(S)) \to ([1, 1, 1, 0], D^d(S))
(n, cont) \to ([1, 0, 0, 0], B(C(D^d(S)))) \to B(C(D^d(S)))
Quick sanity check for hydra(4) = 1114111:
B(C(D(1))) = B(C(C^1(1 + 1))) = B(C(B^2(2 + 1))) = B(C(2^2\cdot (3 + 1) - 1))
= B(C(15)) = B(2^{15} * (15 + 2) - 1) = B(557055) = 2 \cdot ( 557055 + 1) - 1 = 1114111
Let’s define a function that describes the number of cuts required to decrement the i-th depth of the hydra while cleaning up the subsequent spawned heads:
([1, 1, 1, \ldots, h_i, \ldots], x) \to ([1, 1, 1, \ldots, h_i - 1, ...], F_i(x))
Then, based on what’s been demonstrated in the iterated section:
F_{i+1}(x) = F_i^x(x + 1)
where\ F_1(x) = 2\cdot(x + 1) - 1 = 2x + 1
And the answer to the linear hydra game of depth n is:
F_1(F_2(F_3(\ldots F_{n-1}(F_n(1))\ldots)))
To figure out any arbitrary hydra configuration, ([a, b, c, d, e, f, … ], S) you nest the solution for each index inversely with S in the middle to reduce the problem to ([1, 1, 1, …, X], ??). Where ?? is the result of applying all necessary F starting from the first index to reduce the hydra to a single stem.