mersenneforum.org Professor Hercules and the Hydra Herd
 Register FAQ Search Today's Posts Mark Forums Read

 2005-12-07, 17:33 #1 grandpascorpion     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 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 ...
 2005-12-07, 22:54 #2 garo     Aug 2002 Termonfeckin, IE 22×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 2005-12-07 at 22:55
 2005-12-08, 09:13 #3 akruppa     "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
 2005-12-08, 19:42 #4 garo     Aug 2002 Termonfeckin, IE 22·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 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
 2005-12-08, 20:00 #5 garo     Aug 2002 Termonfeckin, IE 22·691 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_{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. Last fiddled with by garo on 2005-12-08 at 20:01
 2005-12-08, 20:54 #6 grandpascorpion     Jan 2005 Transdniestr 503 Posts Or he could just lock his office door.

 Similar Threads Thread Thread Starter Forum Replies Last Post ixfd64 Miscellaneous Math 19 2015-11-23 14:31 ewmayer Lounge 0 2007-04-23 21:13

All times are UTC. The time now is 13:42.

Fri Dec 3 13:42:51 UTC 2021 up 133 days, 8:11, 0 users, load averages: 1.11, 1.13, 1.15