Author |
Topic: 100 prisoners & a light bulb (Read 166729 times) |
|
Anonymous Coward
Guest
|
 |
Re: 100 prisoners & a light bulb
« Reply #275 on: Jul 23rd, 2004, 3:27pm » |
|
on Jul 20th, 2004, 3:15pm, Bitrot wrote:What is wrong with my reasoning?
[B] The knowledge that everyone has been selected constitutes N bits of information. |
|
Wouldn't one bit be enough to convey that information? It depends what the bits mean. Anyway, it is not necessary to know which prisoners have visited, just how many.
|
|
 IP Logged |
|
|
|
LaneMac
Newbie
Posts: 1
|
|
Re: 100 prisoners & a light bulb
« Reply #276 on: Sep 24th, 2004, 11:06pm » |
|
Gonna try to keep it simple optimization is for others.
Im a prisoner what do i know?
1) How many times ive been in the room
2) When in the room: If the light is on or off
I need something else so i assume
3) I know what the cumulative days are
First question i ask is:
Have i been in the room in the last 10 days?
If Yes turn light off and go back to my cell.
If No continue questions.
If the light is on i ask the question:
Have i been in the room MORE times than the value of the ones place of the cumulative days in prison? (0-9) (0=10)
If the answer is yes and the day value is (0). I will call that everyone has been in the room.
If the answer is yes and it is day (1-9) I leave the light on and go back to my cell.
If the light is off I ask the question:
Is it day (1)?
If No then leave light off and go back to my cell.
If Yes then ask:
Have i been in the room more than one time?
If No leave light off and go back to my cell.
If Yes turn light on and go back to my cell.
At worst case you have a series of prisoners that have been in the room 2,3,4,5,6,7,8,9,10,11 times. I haven't worked the probabilities and don't know if i could but in a truly random environment I dont see how this wouldnt be worth the risk.
I believe this is the simplest solution. Other rules will improve assurance but will increase the overall time in prison.
|
|
IP Logged |
|
|
|
Van Luong Nguyen
Guest
|
 |
Re: 100 prisoners & a light bulb
« Reply #277 on: Oct 3rd, 2004, 8:33am » |
|
I believe this solution workx to end up eventually with one prisoner knowing FOR CERTAIN that everyone has been to the living room. Any flaw or error in my thinking? (I did not yet try to estimate the "average" time to get there using my solution, nor to prove that it is optimal or close to optimal).
SOLUTION: Designate only one unique prisoner X who is allowed to turn the light OFF. X always turns the light OFF before leaving the living room. Each of the other 99 prisoners, say A, can never turn OFF a light he finds ON, and can turn ON the light only ONCE, and that is on the FIRST time A finds the light OFF when visiting the living room. Because only X is allowed to turn the light OFF, all prisoners other than X who visit the living room after A has turned it on will leave the light unchanged (ON) until X eventually visits the living room and turns the light OFF. Because each of the 99 prisoners other than X will therefore turn the light on exactly ONCE (the FIRST time he finds the light OFF), which will be seen as ON eventually by X, when X has found the light ON 99 times, he will know FOR CERTAIN that everyone has been to the living room.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 7527
|
|
Re: 100 prisoners & a light bulb
« Reply #278 on: Oct 3rd, 2004, 9:30am » |
|
Yes, it is called the leader solution, given by Caveman (24. Jul 2002 at 09:14).
But it takes an average of 27 years to complete.
We are searching for a way to improve on it, there seem to be solutions that work in 11 or 9.5 years on average.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: 100 prisoners & a light bulb
« Reply #279 on: Oct 8th, 2004, 8:53pm » |
|
For Josh English - I have removed your poll because your proffered solution (everyone can see the bulb and count toggles) has been discussed in the first page or two. At that time, William clarified that the intent is the light is NOT visible from any cell. The only way the prisoners are allowed to communicate with each other is by whether or not they leave the light on when they exit.
As has been mentioned before, there are plenty of "outside the box" solutions. But they are as un-interesting as they are plentiful. What has made this puzzle attract so much attention, and kept people interested in following it, is finding the best "inside the box" solution. This is the challenge.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
brightguy
Newbie
Posts: 2
|
|
Re: 100 prisoners & a light bulb
« Reply #280 on: Oct 16th, 2004, 10:39pm » |
|
Hello everyone... I just stumbled onto this site and got caught up reading the riddle with the pages of proposed solutions. I've read about 10 pages worth, so I am familar with what has already been proposed.
I want to state first off that I use "brightguy" because I'm a lighting designer - not because I think I'm bright.
I want to throw something out there and see if anyone else can do the math. I'll admit that I sucked at all the math courses I took in college (and I have an engineering degree).
The "Leader Theory" sounds logical. BUT, I would think there is one key thing everyone is missing that would maybe cut some time out of this...
In the initial meeting, everyone gets together. Therefore, they can break into 2 groups - MEN and WOMEN. The riddle does say "he or she".
That may not help at all, but I don't think I've read any mention of this. It is too late for me to try to work details, but for some reason I feel like using this male/female ratio could help.
|
|
IP Logged |
|
|
|
brightguy
Newbie
Posts: 2
|
|
Re: 100 prisoners & a light bulb
« Reply #281 on: Oct 16th, 2004, 11:08pm » |
|
I'm not claiming that would help. But after reading some of the other methods, my intuition tells me that adding the sex ratio into the equation might help narrow it down.
During the initial meeting they create groups (lets say there are 50 men & 50 women), they assign a male & female leader & they create rules, and for each rule they set a # of days to abide by it before moving to the next rule:
GROUP: men vs. women
RULE: If you are a MAN, leave the light ON; if you are a WOMAN, leave the light OFF
DURATION: 100 days
GROUP: MEN w/ first names starting w/ A-M vs. everyone else
RULE: If your a man w/ first name from A-M, leave the light ON; otherwise, leave the light OFF
DURATION: 50 days
(other rules would be similar but change the sex and alternate A-n or M-Z)
GROUP: men with first name A-N who've been in the room before vs. everyone else.
RULE: If you've been in the room before and your a guy and you first name is between A-N, leave the light on; otherwise, leave the light OFF.
... and so forth.
I KNOW there is probably more to it than that, but my thinking is that during the initial meeting, the group could determine several ways to break into smaller "trait" groups... whether it is eye color, hair color, sex, name.... and these traits could be implemented into a cycled set of rules to narrow down the field. Of course, I am assuming that these people have memory retention and math skills.
Sorry, I just thought I would throw in my 2 cents. I'll be having constant thoughts of this riddle now that I've stumbled across it.
|
| « Last Edit: Oct 16th, 2004, 11:30pm by brightguy » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: 100 prisoners & a light bulb
« Reply #282 on: Oct 18th, 2004, 6:29am » |
|
You don't need to pick existing physical characteristics to group the prisoners by - you can give each one a unique number from 1 to 100 (or 0 to 99 if you prefer) and then group numbers together however you choose. The problem comes when you try and get useful information out of such a scheme - for instance, if odd numbers (men) turn the light on and even numbers (women) turn it off for the first 100 days, then each person going in knows the parity (gender) of the previous person to go in, but has no idea whether that person has been in before, etc. So on day 101, you have up to 100 prisoners who know up to 2 pieces of information - that at least one odd or at least one even person has been in, or possibly that at least one of each have been in.
Since there's no way to tell which odd-number turned the light on, or which person will find it on, there's no obvious way to turn what information you do get into something useful.
|
|
IP Logged |
|
|
|
Angler
Newbie
Posts: 1
|
|
Re: 100 prisoners & a light bulb
« Reply #283 on: Oct 21st, 2004, 1:36pm » |
|
Grr... just lost the whole thing which I typed.
Here's the gist:
This is likely to be a solution nobody has thought of before. And it is a sick - albeit fast one. Don't read until you are prepared.
You need the prisoner to be able to count to 100 as well as being really brave (or stupid).
Whenever a prisoner enters the living room, if that is before the 100th day from the first day of imprisonment, he or she commits suicide on that day.
Since the warden will (obviously) not choose a dead person, a new prisoner will be picked each day until Day 100 when there is only one left. The said prisoner can safely say that everyone has entered the living room.
My kudos to this problem for giving me the inspiration.
For questions that may be asked:
1. This puzzle only requires you to get someone out as fast as possible. It demands no further conditions.
2. Think this is impossible? Read some news on Middle East and think again.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: 100 prisoners & a light bulb
« Reply #284 on: Oct 21st, 2004, 7:29pm » |
|
William had someone send that "solution" to him in a private e-mail, inventively suggesting ways the prisoners can kill themselves. However, when you suggest the idea in that planning meeting, don't be suprised when your fellow inmates decide to change it to a "99 prisoners & a light bulb" problem right there, thus saving you the need for such inventiveness. 
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
gary84
Newbie
Posts: 1
|
|
Re: 100 prisoners & a light bulb
« Reply #285 on: Oct 23rd, 2004, 8:52pm » |
|
I think "equally randomly" means that every prisoner has been in the room exactly once before any prisoner is selected for the second time. In that case the solution is as follows:
1. if this is the first time you have ever entered in the room and the light is off, turn it on.
2. if this is the first time you have ever entered in the room and the light is on, leave it on.
3. if this is the second time you have ever entered the room and the light is on, turn it off.
4. if this is the second time you have ever entered the room and the light is off, announce everyone has been in the room.
Done.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: 100 prisoners & a light bulb
« Reply #286 on: Oct 24th, 2004, 4:11am » |
|
If I roll an ordinary die, each number, from 1 to 6 comes up equally at random. If I roll the die 6 times and get a different number each time, I get suspicious - the probability of such a thing happening is 5/324 or a little over 1.5%. By the time you have 100 possible outcomes, the chance of getting all 100 in the first100 trials is less than the chance of Earth being hit by an extinction- level meteorite during the time it takes you to read this post...
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: 100 prisoners & a light bulb
« Reply #287 on: Oct 24th, 2004, 2:15pm » |
|
on Oct 23rd, 2004, 8:52pm, gary84 wrote:
I think "equally randomly" means that every prisoner has been in the room exactly once before any prisoner is selected for the second time. In that case the solution is as follows: |
|
In that case, after 100 days everybody can cheerfully announce it is time to go home. Or, if the days are not counted, the first who enters the room for a second time can call for the liberation.
|
|
IP Logged |
|
|
|
ed
Guest
|
|
Re: 100 prisoners & a light bulb
« Reply #288 on: Oct 26th, 2004, 5:04pm » |
|
I don't think the problem can be solved in a reasonable
amount of time, because if the
person say in cell 66 never reports no one would ever
know. At the very least it would require cell 66 to be
called multiple times or during a pre-determined time
which could take years.
We should probably start concentrating on a proof that
the problem cannot be solved in a given amount of time.
What is the minimum amount of information required to
determine that 100 inmates have visited and how much
information is transferred and retained with each 1/0 visit
to the main room.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: 100 prisoners & a light bulb
« Reply #289 on: Oct 26th, 2004, 5:41pm » |
|
It is true that there is no guarantee that the prisoners will ever get free. Since the prisoners are chosen at random, it is possible (vanishingly small, but still possible) that some prisoner never gets chosen. In this case, it would not matter what scheme the prisoners concoct.
This is why all of the various schemes offered here are given in terms of their expected release time - the average time it takes for release to occur. And for that, the current fastest method gives a time of about 9 years (if I remember correctly). Not great, but not that unreasonable either.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
jordan
Guest
|
|
Re: 100 prisoners & a light bulb
« Reply #290 on: Oct 29th, 2004, 5:22pm » |
|
My solution requires a few things to happen:
1. the bulb in the room cools down very slowly
2. there is a clock in the room
3. the prisoners have a thermometer or perfect temperature sensitivity
Let's say at room temperature, when the bulb is off, it is at 65 degrees F. If the bulb is turned on for one minute at the end of the day, it cools down to one degree warmer at the beginning of the next. ex. 1 min on - 66 degrees, 17 min on - 82 degrees.
When the first prisoner comes in he turns the bulb on for one minute at the end of the day and then turns it off. At the beginning of the next day, the next prisoner comes in and takes the temp. reading of the bulb. At the end of the day, he turns the bulb on for one more minute, and then off again. If the prisoner has already come in once, he simply turns the bulb on for the same amount of time as the prisoner before him. When a prisoner comes in and sees that the bulb is at 165 degrees, he will know that all the prisoners have been there, and will tell the guard, and be free to go.
|
|
IP Logged |
|
|
|
Three Hands
Uberpuzzler
Gender:
Posts: 715
|
|
Re: 100 prisoners & a light bulb
« Reply #291 on: Oct 30th, 2004, 5:37am » |
|
Unfortunately, the sadistic guards have a habit of keeping the lightbulb on overnight, and then putting the bulb to the appropriate state of how the prisoners left it the next morning (after all, they do need somewhere to play poker...)
Hence, when the prisoner comes in to find a bulb at 200F the next morning, he's left somewhat confused.
And all this without knowing the potential problem of exponential heat loss (which I think is the case, but I'm not an expert on thermodynamics...)
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: 100 prisoners & a light bulb
« Reply #292 on: Oct 30th, 2004, 12:57pm » |
|
Besides, there's no clock in the room. And, yes, the temperature will tend to suffer exponential decay with the bulb off.
If the bulb were perfectly insulated (not even radiating heat), then you'd still have the problem of judging the temperature - apart from lacking a thermometer, the prisoners also have the problem of getting to the perfectly insulated bulb to measure it...
And when the bulb blows and gets replaced, the prisoners are completely stuck...
|
|
IP Logged |
|
|
|
Vicktor
Guest
|
|
Re: 100 prisoners & a light bulb
« Reply #293 on: Nov 3rd, 2004, 1:28pm » |
|
Maybe something like this would work :
Each prisoner has to keep in mind a counter, starting at 1. Let s call this counter "C".
When entering the bulb room, here is the rule they must follow :
1) "Did i enter the bulb room yesterday ?"
if yes, dont do anything
if no, go to 2
2)
"Is the light bulb ON ?"
if yes, add 1 to my C counter ( C = C + 1 )
if no, C is constant
"Is it the first time i enter the bulb room ?"
if yes, ensure the light bulb is turned ON
if no, ensure the light bulb is turned OFF
If at any time, C = 100, we re free ...
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: 100 prisoners & a light bulb
« Reply #294 on: Nov 3rd, 2004, 1:40pm » |
|
Sorry Vicktor - No dice.
It's highly unlikely that C will ever reach 100. According to your solution - each prisoner may switch the light on only once - but this result will be observed by any one of the remaining 99 prisoners. The count will increment as you describe, but it will be distributed among the prisoners will not be available to one discrete prisoner who can make the declaration for freedom.
|
| « Last Edit: Nov 3rd, 2004, 1:54pm by mattian » |
IP Logged |
|
|
|
Brad711
Newbie
Gender:
Posts: 10
|
|
Re: 100 prisoners & a light bulb
« Reply #295 on: Dec 10th, 2004, 8:13pm » |
|
I"m not a genius, but I think I heard this riddle once. I think maybe it had something to do with the fact that a light bulb heats up... I dono, but maybe you could keep the light bulb on until it burns out... You could alaways shatter the light bulb... or just make up some code system to scratch onto something... Just Ideas.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: 100 prisoners & a light bulb
« Reply #296 on: Dec 11th, 2004, 8:34am » |
|
Brad711, please read the big red note in the header.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Brad711
Newbie
Gender:
Posts: 10
|
|
Re: 100 prisoners & a light bulb
« Reply #297 on: Dec 11th, 2004, 8:39am » |
|
I was thinking... Does the problem have to give a 100% chance of living? If not, there are plenty of shorter solutions that give a 95% chance or so. Anyway, what if there are 4 or 5 leaders, and all of them turn off the light when it is on, just like the leader solution. Exept for that either once it has been off 40 times or so, he or she announces. Or when there are like 3 times in a row where one person has been in(at least 50 days or so apart for each time) and the light is off. I dono, just suggestions. Someone do the math on the 5 leaders thing for the length of time and the probability of dying. Please.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #298 on: Dec 11th, 2004, 9:09am » |
|
This post is found on the first page:
on Jul 23rd, 2002, 11:33pm, Ivo wrote:| Hm, well, a few people have suggested solutions that'll take significantly longer than the prisoners' life spans to work... However, the best one I can come up with is "Wait 3 years and assume (with 99.5% accuracy) that everyone's been in the room".... Anyone got a better solution? |
|
But the classic interpretation of the puzzle is that only 100% certainty is acceptable. Think of the prisoners as being immortal unless killed. Then even the slightest chance of being executed does not make sense.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Rezyk
Junior Member
Gender:
Posts: 85
|
|
Re: 100 prisoners & a light bulb
« Reply #299 on: Dec 11th, 2004, 7:12pm » |
|
I suggest this modification to the problem:
The warden will listen in on all the planning and, if possible, pick an ordering that will result in a false assertion. Otherwise he uses random selection.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Notify of replies
Send Topic
Print