mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2005-12-07, 17:33   #1
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default 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 ...
grandpascorpion is offline   Reply With Quote
Old 2005-12-07, 22:54   #2
garo
 
garo's Avatar
 
Aug 2002
Termonfeckin, IE

22×691 Posts
Default

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
garo is offline   Reply With Quote
Old 2005-12-08, 09:13   #3
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2005-12-08, 19:42   #4
garo
 
garo's Avatar
 
Aug 2002
Termonfeckin, IE

22·691 Posts
Default

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 is offline   Reply With Quote
Old 2005-12-08, 20:00   #5
garo
 
garo's Avatar
 
Aug 2002
Termonfeckin, IE

22·691 Posts
Default

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
garo is offline   Reply With Quote
Old 2005-12-08, 20:54   #6
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default

Or he could just lock his office door.
grandpascorpion is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Nigerian professor claims to have solved Riemann hypothesis ixfd64 Miscellaneous Math 19 2015-11-23 14:31
"You have strucked down Hercules..." 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.