This puzzle has been on the XKCD puzzles wiki for several years. They have some very fun puzzles there. It's a huge timewaster, so only click if you have nothing pressing to do.
http://wiki.xkcd.com/irc/puzzles#Prisoners
If you need help on any of the puzzles, hints and answers are on the talk page. For this specific puzzle, the talk page links to a paper by William Wu that answers this exact question with asymptotic analysis.
This is a really nice puzzle! I didn't know William Wu wrote a paper about it. I saw it many years ago on William Wu's riddles site[1] (highly recommended). It's one of the most popular problems there. The original thread[2] in the forum has 25 pages, covering lots of approaches. There is also another thread[3] summarizing the discussion.
reminds of the good times i had with wuriddles in high school. definitely wasted many hours talking about the 100 prisoner problem and its variants with others back then. another one i liked was the sink the sub one
If you need help on any of the puzzles, hints and answers are on the talk page. For this specific puzzle, the talk page links to a paper by William Wu that answers this exact question with asymptotic analysis.
http://www.ocf.berkeley.edu/~wwu/papers/100prisonersLightBul...