5 ms·

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 nothin

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 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. http://www.ocf.berkeley.edu/~wwu/papers/100prisonersLightBulb.pdf http://www.ocf.berkeley.edu/~wwu/papers/100prisonersLightBul...

andlima 13y ago
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. [1] http://wuriddles.com/ http://wuriddles.com/ [2] http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1027805293 http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board... [3] http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1236693480 http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board...
- jd007 13y ago
  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