Professor Hercules and the Hydra Herd

[grandpascorpion]

This puzzle comes from the Courant Institue of Mathematical Sciences' Holiday 2005 Newsletter.

It was written by Professor Joel Spencer (who wrote the puzzle column "Brain Bogglers" for Discover Magazine from 1987 to 1989).

"The hydra herd is a formidable enemy for Prof. Hercules. Each hydra has some number of heads. At the first stroke ("deletion" for short) a hydra loses one head and then duplicates (starting with a k-headed hydra, yields two (k-1)-headed creatures). The regenerative powers then strengthen; on the next deletion a hydra loses a head and then triplicates. On the n-th deletion a hydra loses a head and then n extra copies of it appear. Moreover, the deletions are counted for the entire herd. Only when a one-headed hydra is deleted does it simply die. Prof. Hercules always deletes a head of the hydra with the least number of heads.

For example, faced with two single-headed and two double-headed (let's write it 2211), Prof. Hercules disposes of the two singles with deletions one and two but deletion three turns a 2 into four 1's, giving 21111. Deletions four through seven leave just 2 standing and deletion eight turns the last 2 into nine singles. These are destroyed one by one. Prof. Hercules's labors end with his seventeenth deletion.

On December 20, 2005 Prof. Hercules walks into his Courant office at 9 a.m. and is confronted with a single four-headed hydra. He applies one deletion every nanosecond. When does he destroy the hydra herd?"

Enjoy ...

[garo]

Nice one. I was surprised how large the number of deletions became. My answer is 15:15:39.

[akruppa]

Neat. Garo, that's the answer I have, but you should have rounded up

What is a better strategy for Prof. Hercules, and how much time would it save him? (Prof. Hercules sure is strong, but it appears that he's none too smart!)

Alex

[garo]

Yeah you are right. 0.98 can easily be rounded up.

The optimal strat is the opposite I think. Chop a head of the hydra with max heads. a 4 headed hydra is done relatively quickly 66 nanoseconds . I tried a seven-headed hydra and found that Prof. Hercules would be done before 10am (9:56:14 to be precise). For an eight headed-hydra I need to write a new program

[garo]

Turns out writing a new program was not required.

For what I think is the optimal strat, the number of deletions increases at each
step according to the following relation.
D_1 = 1

S_n = [(D_{n-1} * (D_{n-1} +1))/2] + 1

D_n = D_{n-1} + S_n

So with a 8-headed hydra, Prof. Hercules is kept busy for 180.59 million years.

[grandpascorpion]

Or he could just lock his office door.