from Hacker News

100 Prisoners and a Lamp

by C-- on 11/24/13, 10:31 PM with 18 comments

• by popularopinion on 11/25/13, 12:05 AM

  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.

  http://www.ocf.berkeley.edu/~wwu/papers/100prisonersLightBul...

• by throwaway0094 on 11/25/13, 12:35 AM

  Give everyone a unique number during the planning phase. Have everyone scratch their number into the wall. Leave the light on.

  When all numbers are on the wall, you are done.

• by brainburn on 11/25/13, 12:44 AM

  The problem description could be a bit clearer. What exactly are the rules?

• by adam-f on 11/25/13, 12:57 AM

  This reminds me of a problem I learned in UCSC (and was accused of cheating by the teacher when I figured it out in five minutes).

  100 Prisoners are told they will be given white or black hats, but they don't get to see the hat they're wearing, they will be lined up facing the same direction, and they gun-to-the-head, say "black" or "white" and if they guess the color of their hat, they get to live.

  They get to speak back to front, i.e., the rearmost prisoner sees all the hats ahead.

  One strategy for optimizing the number left is to speak the color of the hat directly in front of you, in which case the prisoner ahead gets to live by repeating that color. This saves 50%, but of course there's a better solution.