The Hydra

Let $p(h)$ be the probability that we slay the Hydra by killing exactly $h$ heads, where, necessarily, $h = 3n + 1$ for some $n \in \mathbb{N}$ . The probability of doing so is thus $2^{-h}$ , multiplied by the number of ways there are to kill precisely $h$ heads.

For the sake of counting, let's assume the 'split' or 'die' fate of each head slain is predetermined ahead of time. The order of the hero's attacks do not matter. The number of ways to kill precisely $h$ heads is thus the number of ways that a full ternary tree with $h$ nodes can be structured, and that is:

$T(3n+1) = \dfrac{\binom{3n}{n}}{2n+1}$

The probability that the Hydra is eventually slain is the sum of the probabilities that it is slain for all finite numbers of heads for which it may be slain. This summation converges, and it is:

$P = \sum_{n=0}^{\infty} \dfrac{T(3n+1)}{2^{3n+1}}$

Evaluating just a few dozen terms gives us the approximation:

$P \approx 0.61803398874989484...$

$\lfloor 10^{10} P \rfloor = \boxed{6180339887}$

Alternatively, if you don't have a penchant for overthinking things like me, you might realize that $P$ can be defined recursively - the probability of defeating 1 head is equal to the probability of defeating it immediately, plus the probability of it splitting, and then the other 3 heads being eventually defeated, each one being the same.

$P = \frac{1}{2} + \frac{1}{2} P^3$

Algebra yields:

$P^3 - 2P + 1 = 0$

$(P - 1)(P^2 + P - 1) = 0$

This yields three solutions:

$P = -\dfrac{\sqrt{5} + 1}{2}\:\text{or}\:\dfrac{\sqrt{5}-1}{2}\:\text{or}\:1$

The first is negative and can be discarded. The last solution, $1$ , satisfies recursive definitions but is false as it conflicts with the convergent sum definition, which must also hold. Therefore only the intermediate solution, which is equal to $\phi^{-1}$ , where $\phi$ is the Golden Ratio , is correct.

And $\lfloor 10^{10} \phi^{-1} \rfloor = \boxed{6180339887}$

I have an easy programming solution you can formulate a recursion

f( n ) = 0.5( f(n - 1 ) + f(n + 2) )

when f( 0 ) = 1

then we can assume that f( inf ) = 0

for purpose of this problem we can take f( 1000 ) = 0 then we can formulate a system of equation like

Bonus question:

What's the expected number of heads cut if you know you defeated the hydra?

I found $\dfrac{2P}{3-4P}=1+\frac35\sqrt5\simeq2.34$ .

I solved it with:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

var heads={1:1};
var prob=0;
for(var i=1;i<500;i++)
{
    var h={};
    for(var c in heads)
    {
        if(!heads.hasOwnProperty(c))continue;
        var v=heads[c];
        c=parseInt(c,10);
        if(c-1==0){
            prob+=v*Math.pow(.5,i);
        }else{
            if(!h.hasOwnProperty(c-1)){h[c-1]=0;}
            h[c-1]+=v;
        }
            if(!h.hasOwnProperty(c+2)){h[c+2]=0;}
            h[c+2]+=v;
    }
    heads=h;
}
console.log(Math.floor(Math.pow(10,10)*prob));

I also solved it with PHP to take advantage of longer execution time and more precision:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

<?php
define('SCALE',100);
set_time_limit(60);
$prob='0';
$heads=array(1=>'1');
for($i=1;$i<=1000;$i++)
{
    $h=array();
    foreach($heads as $c=>$v)
    {

        if($c-1==0){
            $prob=bcadd($prob,bcmul($v, bcpow('.5',"$i",SCALE),SCALE),SCALE);
            }else{
            if(!array_key_exists($c-1, $h)){$h[$c-1]='0';}
            $h[$c-1]=bcadd($h[$c-1],$v,SCALE);
        }
            if(!array_key_exists($c+2, $h)){$h[$c+2]='0';}
            $h[$c+2]=bcadd($h[$c+2],$v,SCALE);
    }
    $heads=$h;
}
echo $prob;
?>