RPG Superstar 2010 Top 16
|
Randall Munroe, the creator of the xkcd webcomic, maintains a wiki of very clever puzzles. This is one of my favorites, because the answer is difficult to arrive at, but blatantly obvious in retrospect. Which is, I suspect, a plausible operating definition of "genius".
100 people are being held prisoner in a jail. They are told that in one hour, they will all be taken to separate windowless, soundproof cells. One at a time, and in a random order, they will be taken from their cells, interrogated, and then sent back to their cells. All interrogations will take place in the same room, which contains one light bulb and the switch that operates it. The light is initially off, but the inmates are free to toggle the switch as often as they want, whenever they are in the interrogation room, and the prison guards will not toggle the switch at all. No prisoner can see the light from his cell. Only one prisoner is interrogated at a time, each prisoner can be interrogated multiple times, and they have no way of communicating besides the light switch. The length and amount of time between interrogations is random, so no help there.
At any time, any prisoner under interrogation may state, "Everyone has been interrogated at least once." If this statement is true, everyone will be released. If it is false, all of the prisoners will be executed.
The prisoners have one hour to work out their strategy before they're isolated for good. How do they get released?
Note: The selection process for interrogations is random and fair; some prisoners may be interviewed multiple times before another prisoner is interrogated at all, and after any point in time, every prisoner will be interrogated an infinite number of times more.
I think the solution will involve the average lifespan of a lightbulb.
So if the lightbulb has an expected lifespan of 1000h then every prisoner should turn on the lamp for the fist 10 hours he is interrogated.( and try once each session for 1 second if the bulb still works)
So if the bulb burns out during any interrogation it's pretty safe to assume that every prisoner has been interrogated at least around 10 hours.
|
Got it! Do not read if you are still trying to come up with the answer.
Procedures for the leader: If he enters the room and the light is off, he does nothing. If he enters the room and the light is on, he turns it off and counts that as 1. When he enters the room and the light is on for the 99th time, he declares that everyone has been interrogated.
Other prisoners: If they enter the room and the light is on, they do nothing. If they enter the room and the light is off, they turn it on, but that is only for the first time they encounter the light being off. Any subsequent times they enter and the light is off, they do nothing.
|
Edit: ninja'd by Celestial Healer, whose method is slightly quicker.
|
|
Very nice, both of you.
Is there any solution if the prisoners are not sure of the initial position of the lightswitch? (That is, it might start either on or off.)
For all "leader"-type strategies: What happens if they interrogate selected other more "suspicious" prisoners like 10,000 times before the leader ever gets called once? They could all die of old age or cumulative torture effects before ever being released. I assume part of any "correct" (i.e., workable) solution is that they get released within a reasonable time span?
|
RPG Superstar 2010 Top 16
|
Kirth,
The choice of which prisoner to select is random, as in d100. So it's quite possible that it could take a very long time for the plan to work. But "after any point in time, every prisoner will be interrogated an infinite number of times more." So the determining process will terminate eventually.
never mind, that won't work...
Not quite, but you're very close.
|
|
Kirth,
The choice of which prisoner to select is random, as in d100. So it's quite possible that it could take a very long time for the plan to work. But "after any point in time, every prisoner will be interrogated an infinite number of times more." So it will terminate eventually.
never mind, that won't work...Not quite, but you're very close.
Hah! I've just realised I'm an idiot!
Since one prisoner could theoretically be interrogated an infinite amount of times, this is technically impossible. Correct me if I'm wrong, I'm pretty sure I am. Has the answer been stated yet?
|
RPG Superstar 2010 Top 16
|
Kobold Cleaver, prisoners are interrogated at random. The phrase "after any point in time, every prisoner will be interrogated an infinite number of times more" may be taken to mean that every prisoner will eventually be interrogated after some (perhaps very long but) finite time.
And yes, good answers have been posted.
The choice of which prisoner to select is random, as in d100.
Ugh. The applied scientist in me hates these "ethereal plane" scenarios. Switches that are invisible to employees; light bulbs that never burn out; random generation of prisoners to interrogate... I always prefer scenarios where I can take advantage of the laws of physics, circumstances outside the puzzle designer's radar, and/or of flaws in human nature.
Kobold Cleaver, prisoners are interrogated at random. The phrase "after any point in time, every prisoner will be interrogated an infinite number of times more" may be taken to mean that every prisoner will eventually be interrogated after some (perhaps very long but) finite time.
And yes, good answers have been posted.
Meh. I'm probably biased, since I flunked here, but it seems to me that there has been nothing in this puzzle which would indicate that there is any set point at which every prisoner has to have been interrogated. I can't figure out any way for them to count, either. I've even read the spoilers people posted, but none of them seemed 'obvious' to me, which probably proves that I am not a genius.
The choice of which prisoner to select is random, as in d100.Ugh. The applied scientist in me hates these "ethereal plane" scenarios. Switches that are invisible to employees; light bulbs that never burn out; random generation of prisoners to interrogate... I always prefer scenarios where I can take advantage of the laws of physics, circumstances outside the puzzle designer's radar, and/or of flaws in human nature.
{sighs... puts away radioactive isotope, Geiger counter, and hydrocyanic acid for Kirth-based experiment}
|
RPG Superstar 2010 Top 16
|
Ugh. The applied scientist in me hates these "ethereal plane" scenarios. Switches that are invisible to employees; light bulbs that never burn out; random generation of prisoners to interrogate... I always prefer scenarios where I can take advantage of the laws of physics, circumstances outside the puzzle designer's radar, and/or of flaws in human nature.
"Assume a perfectly spherical cow..."
Oh, the interrogators know about the light switch; they just promise they won't use it themselves. The light just needs to burn for the time it takes the process to complete. Figure that's about 10,100 interrogations, on the average. At ten interrogations per day, that's not even three years.
Meh. I'm probably biased, since I flunked here, but it seems to me that there has been nothing in this puzzle which would indicate that there is any set point at which every prisoner has to have been interrogated. I can't figure out any way for them to count, either. I've even read the spoilers people posted, but none of them seemed 'obvious' to me, which probably proves that I am not a genius.
There's no pre-set point, but the choice of prisoners to interrogate is indeed random, and every prisoner will eventually be interrogated, an indefinite number of times. It's not just unlikely that the interrogators will never choose, say, Prisoner #62, it's guaranteed that they'll pick him. And if the interrogations go on indefinitely, they'll keep picking him.
For counting,
Let's say that there is a chalkboard in the room instead of a light switch, and each prisoner gets a chance to put a tally mark on the board, once. The leader knows that, once he sees 99 tally marks, he can make the announcement. With the light switch, once he sees the light turned on for the 99th time, he knows that each other prisoner has been in the room and signaled him, and he can announce that.
Meh. I'm probably biased, since I flunked here, but it seems to me that there has been nothing in this puzzle which would indicate that there is any set point at which every prisoner has to have been interrogated. I can't figure out any way for them to count, either. I've even read the spoilers people posted, but none of them seemed 'obvious' to me, which probably proves that I am not a genius.There's no pre-set point, but the choice of prisoners to interrogate is indeed random, and every prisoner will eventually be interrogated, an indefinite number of times. It's not just unlikely that the interrogators will never choose, say, Prisoner #62, it's guaranteed that they'll pick him. And if the interrogations go on indefinitely, they'll keep picking him.
For counting, ** spoiler omitted **
...
.....Color me embarrassed.
For there record, I wasn't far. I got everything except the 'only the first time' bit. That's what hung me up. In retrospect, it's beyond obvious, especially since I had everything else. I got stuck on what should have been the easy bit. o_O
Nice puzzle.
|
I like this my answer.
** spoiler omitted **
That was sort of a variant on what I almost put down as my answer (unfortunately, I made the mistake of asking if the prisoners can kill the guards, which screwed the s&*% out of my plan). Years of Scout camp have filled me with that kind of stuff.
My favorite is the Man on the Moon misdirection gig.
The obvious answer, Ask the guards. At no point in the puzzle was it stated the guards would lie or refuse to answer. Granted, that's cheating, but it's more amusing than the other answers.
The obvious answer, Ask the guards. At no point in the puzzle was it stated the guards would lie or refuse to answer. Granted, that's cheating, but it's more amusing than the other answers.
Ooh! Just got an idea!
Can the prisoners ask the guard?
Every time a prisoner is interrogated during the day, he or she ignores the switch. When a prisoner is interrogated at night, he or she pulls the switch to turn the lights off and escapes in the confusion.
|
|
my Fav!
Smurfs and Gargamel
Gargamel has captured 100 Smurfs. Feeling confident he proposes the following game:
He will exchange the white hats of an undefined number of smurfs with red hats. No smurf knows his own color. All smurfs can see each other, but they have no other means of communication. Then, each Smurf (order selected by Gargamel) should say the color of his hat (loudly so that everyone can hear it). If it is correct, then he lives, otherwise he dies.
After a short discussion the smurfs accept. They know that the first Smurf to be chosen might die, but all 99 other smurfs will survive.
How?
Hey, Chris is adding more rules to the puzzle! No fair!
Berik: Actually, Kirth, Entropi, Squeak and I gave answers which did not require a leader. Some others probably did, too. Although only mine and Squeak's came before your post.
/\ All sm**fs immediately forfeit and die. :)
I think I got it...
A few things have to be agreed to ahead of time.
1. If any prisoner other than the Erik enters the room to find the bulb off, and they've not been interrogated before, they must turn it on. Also, if they find the bulb on, they must not touch the switch.
2. If Erik enters the room and finds the bulb turned off, he doesn't touch the switch, but if the bulb is on, he switches it off. Starting with the number one - representing his own first interrogation - he adds +1 each time he finds the switch on and has to switch it off, and upon reaching the count of 100 states that everyone has been interrogated once, flips the bird to the man, kick over the table, throws his hands up in the air and shouts "We outta here!"
Actually, the sm**f one was easier than the prisoner one, but I'm reluctant to risk messing up and getting sm**f'd. :P