7 ms·

100 Prisoners and a Lamp

39 points by C-- 13y ago

popularopinion 13y ago
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
throwaway0094 13y ago
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.
- Ellipsis753 13y ago
  This is an amazing solution. Of course the light is needed or they couldn't see the wall!
- crazygringo 13y ago
  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.
- FalcorTheDog 13y ago
  "they won’t be able to communicate again until the game is over." Clearly, this would be a form of communication between the prisoners.
  - comex 13y ago
    So is the light. Reminds me of this: http://blogs.msdn.com/b/ericlippert/archive/2011/02/14/what-would-feynman-do.aspx http://blogs.msdn.com/b/ericlippert/archive/2011/02/14/what-...
- shootTheHostage 13y ago
  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?
  - throwaway0094 13y ago
    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. ;-)
brainburn 13y ago
The problem description could be a bit clearer. What exactly are the rules?
- spacehome 13y ago
  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.
adam-f 13y ago
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.
- mikeash 13y ago
  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?
  - ssfermoy 13y ago
    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.
    - Ellipsis753 13y ago
      That's awesome. To me it seems like a parity bit for RAID or an error-correcting code.
    - mikeash 13y ago
      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.
deleted 13y ago
[deleted]
deleted 13y ago
[deleted]

39 points by C-- 13y ago

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

throwaway0094 13y ago

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.

Ellipsis753 13y ago
This is an amazing solution. Of course the light is needed or they couldn't see the wall!
crazygringo 13y ago
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.
FalcorTheDog 13y ago
"they won’t be able to communicate again until the game is over." Clearly, this would be a form of communication between the prisoners.
- comex 13y ago
  So is the light. Reminds me of this: http://blogs.msdn.com/b/ericlippert/archive/2011/02/14/what-would-feynman-do.aspx http://blogs.msdn.com/b/ericlippert/archive/2011/02/14/what-...
shootTheHostage 13y ago
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?
- throwaway0094 13y ago
  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. ;-)

brainburn 13y ago

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

spacehome 13y ago
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.

adam-f 13y ago

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.

mikeash 13y ago
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?
- ssfermoy 13y ago
  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.
  - Ellipsis753 13y ago
    That's awesome. To me it seems like a parity bit for RAID or an error-correcting code.
  - mikeash 13y ago
    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.

deleted 13y ago

[deleted]

deleted 13y ago

[deleted]