100 Prisoners and a Lamp | Hacker News Reader

100 Prisoners and a Lamp

theccontinuum.wordpress.com

39 pointsC--18 comments

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...

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/

[2] 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...

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

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.

This is an amazing solution. Of course the light is needed or they couldn't see the wall!

Heck, you don't even need to pick numbers in advance. Just pick a number the first time you go in the room, that isn't already on the wall.

Or use names, symbols, it doesn't matter. Just wait until there are 99 different ones on the wall.

"they won’t be able to communicate again until the game is over."

Clearly, this would be a form of communication between the prisoners.

So is the light.

Reminds me of this:

http://blogs.msdn.com/b/ericlippert/archive/2011/02/14/what-...

This is a clever and practical idea, in the sense of having Indiana Jones just shoot the guy with his pistol, instead of engaging in an elaborate sword fight, but it violates the spirit of the problem. If we solved all of our problems like this, we would kill the patients instead of curing the diseases.

The premise of the problem is very clear: How do you tally the presence of 100 unique events, some of which may repeat themselves, when you may use one and only one bit to register the state of the system?

It depends on the disease, doesn't it? At this point (for some diseases) it's much more cost-effective to kill the patient that would have gone towards prolonging a state of suffering. Then send the funds towards Against Malaria or something else. ;-)

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

This is a pretty poor description of the problem if you've never heard of it before. The salient information is that there is a single binary switch in the room that can be turned to an 'on' or 'off' position. The prisoners entering the room can observe what the state of the switch is when they enter, and they have the option to flip the switch or not.

Also, one of the prisoners is not a 100-bit accumulator. He or she would be a 7-bit accumulator (128 > 100), but this is a very tortured way to say that this one prisoner can count to 100.

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.

Spoiler ahead! Potential answer!

My solution is that the first prisoner states the color of the hat in front of him, the second prisoner states the color he just heard, and so forth with odd and even numbers until you get to the end. This saves 75% (even numbers are guaranteed to live, odd numbers live with 50% odds).

Is this optimal?

If they decide the guy at the back indicates an odd number of black hats by saying white or an even number of black hats by saying black. Now the remaining prisoners all live and the back guy has a 50/50 shot.

That's awesome. To me it seems like a parity bit for RAID or an error-correcting code.

Very nice. It took me a while to see why that works, so I wonder how long it would have taken me to come up with it.

Now that I get it, it seems almost obvious. It's basically the same as my solution, except I'm essentially using this technique on 50 separate lines of 2 people each.

Glad you like it. Heard this as an interview question at a trading company. Gave something similar to your solution and was asked for a better one, eventually work my way to the solution above but was given no indication if it was what they wanted. It wasn't a pleasant experience.

Reply on news.ycombinator.com