20051207, 17:33  #1 
Jan 2005
Transdniestr
503 Posts 
Professor Hercules and the Hydra Herd
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 kheaded hydra, yields two (k1)headed creatures). The regenerative powers then strengthen; on the next deletion a hydra loses a head and then triplicates. On the nth 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 oneheaded 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 singleheaded and two doubleheaded (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 fourheaded hydra. He applies one deletion every nanosecond. When does he destroy the hydra herd?" Enjoy ... 
20051207, 22:54  #2 
Aug 2002
Termonfeckin, IE
2^{2}×691 Posts 
Nice one. I was surprised how large the number of deletions became. My answer is 15:15:39.
Last fiddled with by garo on 20051207 at 22:55 
20051208, 09:13  #3 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
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 
20051208, 19:42  #4 
Aug 2002
Termonfeckin, IE
2^{2}×691 Posts 
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 sevenheaded hydra and found that Prof. Hercules would be done before 10am (9:56:14 to be precise). For an eight headedhydra I need to write a new program 
20051208, 20:00  #5 
Aug 2002
Termonfeckin, IE
ACC_{16} Posts 
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_{n1} * (D_{n1} +1))/2] + 1 D_n = D_{n1} + S_n So with a 8headed hydra, Prof. Hercules is kept busy for 180.59 million years. Last fiddled with by garo on 20051208 at 20:01 
20051208, 20:54  #6 
Jan 2005
Transdniestr
503 Posts 
Or he could just lock his office door.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Nigerian professor claims to have solved Riemann hypothesis  ixfd64  Miscellaneous Math  19  20151123 14:31 
"You have strucked down Hercules..."  ewmayer  Lounge  0  20070423 21:13 