Post by dodrudon on Sept 4, 2007 22:49:33 GMT
I'm wondering if this collection here of freaks and geeks are puzzle enthusiasts. Let's find out! The puzzles will be posted in "PUZZLE: [puzzle name]" threads, please post hints, questions, discussions, everything but the answer here. If you think you know the answer, please post it in a thread titled "ANSWER: [puzzle name]" so it can be subjected to much subjection.
Again, discussions, hints, NO ANSWERS in the "PUZZLE: [puzzle name]" threads.
Here's the puzzle:
There is a warden, 100 prisoners (the number of prisoners doesn't matter), and a lightbulb which starts in the off state. The warden makes a deal with the prisoners, he'll let them all go free if they can beat his challenge. The challenge is this: the warden will prepare a room, within which will be nothing but the aforementioned light bulb, and a switch to control the lightbulb. The warden will randomly, at random times, choose a prisoner to bring into the the room. At this point, the prisoner can choose to flip the switch, or choose not to flip it. If at any time a prisoner correctly tells the warden that all 100 prisoners have visited the room, they go free. Otherwise they're put on death row. They only get one guess.
Assume that the warden won't do anything evil like bring only one person in to the room forever. Also assume that any prisoner will visit the room within an unspecified, but finite, and reasonable time in the future. You cannot use this time in the solution ("wait 100*the length of the reasonable time" for example).
The prisoners get to convene first in order to discuss a strategy. Afterwards they will be confined to their cells and no communication (except through the lightbulb in the room) between them will occur. You, of course, are one of those prisoners (wrongfully imprisoned, no doubt), and wish to be set free (along with 99 other miscreants). What's the strategy?
In a harder version of the puzzle, the initial on/off state of the lightbulb is unknown. What is your strategy now?
Again, discussions, hints, NO ANSWERS in the "PUZZLE: [puzzle name]" threads.
Here's the puzzle:
There is a warden, 100 prisoners (the number of prisoners doesn't matter), and a lightbulb which starts in the off state. The warden makes a deal with the prisoners, he'll let them all go free if they can beat his challenge. The challenge is this: the warden will prepare a room, within which will be nothing but the aforementioned light bulb, and a switch to control the lightbulb. The warden will randomly, at random times, choose a prisoner to bring into the the room. At this point, the prisoner can choose to flip the switch, or choose not to flip it. If at any time a prisoner correctly tells the warden that all 100 prisoners have visited the room, they go free. Otherwise they're put on death row. They only get one guess.
Assume that the warden won't do anything evil like bring only one person in to the room forever. Also assume that any prisoner will visit the room within an unspecified, but finite, and reasonable time in the future. You cannot use this time in the solution ("wait 100*the length of the reasonable time" for example).
The prisoners get to convene first in order to discuss a strategy. Afterwards they will be confined to their cells and no communication (except through the lightbulb in the room) between them will occur. You, of course, are one of those prisoners (wrongfully imprisoned, no doubt), and wish to be set free (along with 99 other miscreants). What's the strategy?
In a harder version of the puzzle, the initial on/off state of the lightbulb is unknown. What is your strategy now?