Author |
Topic: 100 prisoners & a light bulb (Read 167801 times) |
|
Captain Caveman
Guest
|
 |
100 prisoners & a light bulb
« on: Jul 23rd, 2002, 10:50pm » |
|
Argh, I made the mistake at looking at the 100 prisoners & the light bulb one (under Favorites). It's driving me crazy... I can't even begin to think of the solution... and there's no hint with it...
Can anybody help? (hint is nice. solution is better. solution w/explanation gets you a gold star  )
//Title changed by moderator//
|
| « Last Edit: Sep 1st, 2003, 7:45pm by Icarus » |
 IP Logged |
|
|
|
Ivo
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #1 on: Jul 23rd, 2002, 10:55pm » |
|
I've been puzzling over this one as well.. googling doesn't seem to help, yet... My best guess is that it has something to do with taking a very long time and taking advantage of the fact that the prisoners know how many days it's been since the start...
|
|
IP Logged |
|
|
|
Garth Johnson
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #2 on: Jul 23rd, 2002, 11:10pm » |
|
Unless it's a trick, I'm sure this is related to probability, which I've nearly forgotten. Initially probably something along the lines of:
don't flip the switch the first time you've been to the room. (after 100 days) Then each subsequent time you've been to the room (or nth time?) toggle the switch to the opposite of what it was the previous time (left the room on last time, leave it off this time). Probability should drop rapidly for each visit where the light encounter is the same as the previous (if on when left and off when entered).
Hmm. this made more sense before I started writting it down.
|
|
IP Logged |
|
|
|
mESSDan
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #3 on: Jul 23rd, 2002, 11:17pm » |
|
Maybe the answer is this:
Only turn on the switch if you have never been in the room before. If you've been in the room before, turn the light off.
If you've been in and the light is on, you know the last person hadn't been in there before. As soon as you've been in the room atleast 99 times with the light being on, you've got it.
I like the fact that I'm probably wrong
|
|
IP Logged |
|
|
|
BanderSnatch
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #4 on: Jul 23rd, 2002, 11:19pm » |
|
My first thought on this is rather simple, though in reality it would (most likely) take far too long to be practical. Starting the day of the meeting, each prisoner starts counting the days. As each prisoner goes into the room, they leave the light in the off position. However, if they have been in the room once before in the hundred days, they turn the light on. Once the light is turned on, it stays on for the remainder of the initial hundred days as a signal to the others that someone has been in the room more than once, and hence someone will not have been in the room at the end of the hundred days. On the hundredth day, the prisoner turns the light off, starting another hundred day cycle. If, on the last day of any hundred day cycle, the light remains in the off position, it can be said with certainty that every prisoner has been in the room, since no prisoner has been there twice.
Though this solution would eventually work, probability says that it would not work in a timely manner, since it goes in 100 day cycles, rather than having the possibility of the hundred days starting at any arbitrary time.
|
|
IP Logged |
|
|
|
Ivo
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #5 on: Jul 23rd, 2002, 11:33pm » |
|
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?
|
|
IP Logged |
|
|
|
Captain Caveman
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #6 on: Jul 23rd, 2002, 11:34pm » |
|
Well... inelegant, but certainly workable. At least I can go to bed now without it bothering me too badly.
Since the page doesn't indicate he's missing the solution for this one, I hope Mr. Wu is kind enough to post his solution here.... I keep wondering if there's a really simple easy one or something.
|
|
IP Logged |
|
|
|
Daleks
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #7 on: Jul 23rd, 2002, 11:35pm » |
|
First off, the problem statement never says whether or not the prisoners can see the light flickering in their cells. I'll assume they can. Also there will come a time that all prisoners will have entered the commons area. Whether or not they die before that time comes is a problem, but I'll ignore that.
Anyway, my idea is to have each prisoner remember the number of times the light was flicked on/off the night before--call it n. If they have never been in the commons area before and are selected the next day, they flick the light n+1 times. If they have been in the commons area before and are selected, flick the light n times. And of course if they're not selected, sulk in their cell. So the person that enters the commons area and would have flicked the light 100 times can merely tell the warden everyone has been inside. You could also just not flick the light at all if you're a repeat, but people might forget. Also of course n starts at 0.
|
|
IP Logged |
|
|
|
Captain Caveman
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #8 on: Jul 23rd, 2002, 11:36pm » |
|
Err, I meant the 100-day cycle one was inelegant but workable. It'd take forever, but at least you'd be *certain*, which is the impression I took from the way the riddle is posed -- you'd be CERTAIN your answer was correct.
|
|
IP Logged |
|
|
|
Captain Caveman
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #9 on: Jul 23rd, 2002, 11:39pm » |
|
Hrm, the counting flickers is interesting. I just assumed the "solitary" bit meant that they were totally isolated.
These are really the kind of questions you need to be on a one-on-one basis so you could ask questions like that of the riddler... "Can they see the light from their cells?" ("Yes" "No" "irrelevant")
|
|
IP Logged |
|
|
|
Captain Caveman
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #10 on: Jul 23rd, 2002, 11:46pm » |
|
Ok, here's 2 i snagged quickly from /. that I like.
1: Designate 1 person to turn the light off. Everyone else, on your first time in the room, IF THE LIGHT IS OFF, turn it on. (Otherwise, leave it on.) After the designated person turns it off 99 times (or 100, if he turns it off for himself...), he can demand their freedom.
This works even if they can't see the bulb from their cells and is rather elegant.
2: If they can see the bulb, instead of flicking it a whole bunch of times, just flick it once on your first time in the room. After the 100th flick, demand freedom.
|
|
IP Logged |
|
|
|
SPEEDenator
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #11 on: Jul 23rd, 2002, 11:50pm » |
|
The solution works IFF (that's the iff and only iff bit there) in a given 100-day cycle, all 100 prisoners go in... there are plenty of patterns (granted, not necessarily random  that foil it:
day 1: prisoner 1 goes in
day 2 - cycle in order prisoners 1 - 100
Thus, there's always 1 person who will have seen the light twice in that cycle.
-e
|
|
IP Logged |
|
|
|
BanderSnatch
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #12 on: Jul 23rd, 2002, 11:53pm » |
|
If the light could be seen by each inmate, it would make the problem quite trivial. The idea posted earlier of flicking the light n number of times would work, but would actually be overly complicated.
Assuming the inmates can see the light from their cells, they would simply have to set up the following system:
If you have not been in the room before, turn on the bulb for a set time and turn it back off.
If you HAVE been in the room before, do not turn on the bulb at all.
The prisoners count the number of times the bulb comes on. After they count to 100, everyone has been in the room.
Problem: The riddle states that the bulb may be toggled, but it does not say how many times. If the inmate may only toggle it once (ie from off to on, or on to off), this plan would not work without modification. In which case the following ruleset would be better:
If prisoner has not been in the room before, they turn the light on and leave it on.
If prisoner HAS been in the room before, they turn the light off, and it stays in the off position until another inmate turns it on. Inmates must then only count the number of days the light is on. Once the number reaches 100, everyone has been there.
The problem with both these very similar solutions is that both assume, possibly (probably?) incorrectly, that the inmates can see the light from their cells.
|
|
IP Logged |
|
|
|
SPEEDenator
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #13 on: Jul 24th, 2002, 12:14am » |
|
Men-in-Black Solution:
If the lightbulb is off, turn it on.
First time in the room, carve a "I" into a wall. When there are 100 "I"s, you're done.
Last one out turn off the light.
The "99 turn offs until you're done" I think amounts to 100! if the distribution is close to cylcical (i.e. say guy 1 is turn-offer, if it goes 1 .. 100 and then cycles again, it'll be 100!). But hey, after 100! days, they'll all be free.
-e
|
|
IP Logged |
|
|
|
DTM
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #14 on: Jul 25th, 2002, 1:16am » |
|
This one had me going for a bit too.
I really think Captain Caveman has the essence of the solution, however since the guards take a prisoner at random, you are wasting a lot of time waiting for the designated person to show up to start the whole thing off.
The prisoners should decide that whoever is the first prisoner to enter the room after their huddle is the leader (as 'elected' by the guards).
He turns on the light, and is the only person allowed to turn on the light.
Each and every other prisoner turns off the light if and only if the light is already on and if they have not already done so.
When the leader turns on the light for the 100th time (this includes the first one), time to be free! Of course, as the leader has to himself/herself return to the room 100 times, it could take over 27 years...
Slightly better yet, they could choose that whoever enters the room on the 2nd day after their meeting is the 'elected' leader, and declared freedom when he turns the light on for the 99th time (he assumes the light was off when he got in on day 2). If it's the same person on the 2nd day as the 1st, then it's the same as the first solution, otherwise they can save one leader cycle which could last from a few days to a hundred (or far more) days.
I think the best that this can be optimized is to have the person who enters the room on the 3rd day, the elected leader. The first person turns the light on. If he's also the person in the room on the 2nd day, he leaves it on. Otherwise, the 2nd person turns off the light. The third person (or 'elected' leader) needs to turn on the light 98 times if he comes in with the light off, 99 times if the light is on, or 100 times if the guards were nasty and made it the same person for the 1st three days...
If there is another improvement, I can't think of it at this time!
Note: As they are in isolation, it is unlikely that they can either see the flicker (besides, they'd have to be fully and continuously aware - doubtful if your left in isolation for too long !) And they better pray there isn't an electrical storm or that the bulb doesn't burns out during the minimum 100 days! Then again, if a prisoner dies somewhere along the way, they're doomed!
|
|
IP Logged |
|
|
|
scodger
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #15 on: Jul 25th, 2002, 5:12am » |
|
The prisoners are allowed to get together one night, to discuss a plan. What plan should they agree on, so that eventually, someone will make a correct assertion?
it doesnt say it has to be the firdst day, maybe this is the key
|
|
IP Logged |
|
|
|
knox
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #16 on: Jul 25th, 2002, 6:13am » |
|
Yes a hybrid might be a good way.
Say just wait for hundret days. Then make the meeting night. Now you can count how many people have already been to the room and how many are missing. I think with random chances ~50% of the people should have been in the room already. (after 200 days 75%, etc.)
So you should calculate when you get the shortest time in result to make metting time, this is where probality caluclation comes in.
Okay after meeting night you have two groups, the ones who have already been in there and the ones who havent. Then you can do the leader system as descriped before. Or is there something better? Those who have been in there before meeting night of course don't touch the light any more.The ones who havent turn the light on if it's off and they haven't yet turned it on. The leader turns it off everytime he is in. After he turned it n times off he can demand freedom.
--
For the theories where the prisoners can see the light from the cells, they don't need to "flicker" it at all (so breaking the rules). Just toggle it over the first time you are in the room. (if it has been on turn it off, it has been of turn it on) After they have seen it hundret times toggling they can demand freedom safely.
--
Then there is a pragmatic way also, just wait say 365 days without caring about the bulb at all and then demand freedom to take your chances, A year prision is long enough. (or two years or three, etc. your chances go better).
|
|
IP Logged |
|
|
|
dmachine2
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #17 on: Jul 25th, 2002, 8:18am » |
|
Well, they're allowed to meet all together one night. Why not meet in the living room?  It's probably the only room that can hold all the prisoners anway
|
|
IP Logged |
|
|
|
AGirl
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #18 on: Jul 25th, 2002, 9:11am » |
|
The fastest way to get the cons out (without resorting to weasles like marking things on the wall or being able to see the light) I can find is the following:
Info: 100 cons, 1 bit info transfer, random selection of cons.
You can only work in cycles of 100 days. Someone posted that solution already, but in stead of resetting every cycle you should reset but keep counting cycles.
The cons agree that they do not swich on the light, unless they have visited the room more than once in the first cycle. If the light is switched on by someone, the cons know that soemone has been in twice and that at least one person has not visited the room. They have to wait until the end of the cycle and don't do anything.
The first one to start the second cycle switches off the light if he has been in the room twice or less (twice, because it's the second cycle). The light stays out unless someone comes into the room who has been in the room three times or more. Then the light goes on. If the light is on, it stays on for the rest of the cycle and the cons, again, know that chances are that at least one person has not been in the room and do nothing. In the third cycle the light only goes on if someone has visited 3 or more, in the 4th cycle 4 or more, etc.
If OTOH, at the end of a cycle, the light is out (i.e. every con has visited the room a number of times that is equal or less to the number of cycles that have passed) the first con of the next cycle can declare freedom.
This solution is better than the one posted where the cycle just gets reset every time, because in that case you have to wait until the random selection happens to pick every con exactly one time within a 100 day cycle.
This solution does not require that, as it keeps track of the number of cycles and thus minimises the number of repeats required.
It can still take a long time, but speed is not a requirement of the riddle. Accuracy is. "Taking your chances" is not a valid solution.
|
|
IP Logged |
|
|
|
DTM
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #19 on: Jul 25th, 2002, 11:29am » |
|
All I can say is, poor prisoners!
So far, two workable solutions given a reasonable definition of solitary confinement.
The 'leader' solution could take 27 years, while either of the 100 day cycle ones might never occur.
In the first variant, as AGirl pointed out, it takes that all 100 prisoners get perfectly distributed over an arbitrarily fixed 100 day period. While the second variant isn't necessarily better as it requires a different perfect distribution in that each prisoner enters the room n times in a arbitrarily fixed set of n*100 days.
Both systems are at the mercy of the jailers. I might be more tempted with the 2nd 100 day cycle solution if I knew that the warden was using a pseudo-random number generator (it generally NOT being truly random) thus more likely to be uniformly distributed. This one seems better suited for a computer algorithms than real life.
I prefer the leader solution as it doesn't require that every prisoner keep track of exactly how many days they've been in solitary confinement (a difficult task at best!). Plus, it can take advantage of the scodger/know variant of waiting before the first meeting, which I can't see it being of use to the 100 cycle day variants. Granted, it is less likely to have a quick resolution...
Anyone have a valid third solution that doesn't require 'cheating' by seeing the light while in solitary confinement? (I like the idea of having the meeting in the living room!)
|
|
IP Logged |
|
|
|
DTM
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #20 on: Jul 25th, 2002, 11:34am » |
|
All I can say is, poor prisoners!
So far, two workable solutions given a reasonable definition of solitary confinement.
The 'leader' solution could take 27 years, while either of the 100 day cycle ones might never occur.
In the first variant, as AGirl pointed out, it takes that all 100 prisoners get perfectly distributed over an arbitrarily fixed 100 day period. While the second variant isn't necessarily better as it requires a different perfect distribution in that each prisoner enters the room n times in a arbitrarily fixed set of n*100 days.
Both systems are at the mercy of the jailers. I might be more tempted with the 2nd 100 day cycle solution if I knew that the warden was using a pseudo-random number generator (it generally NOT being truly random) thus more likely to be uniformly distributed. This one seems better suited for a computer algorithms than real life.
I prefer the leader solution as it doesn't require that every prisoner keep track of exactly how many days they've been in solitary confinement (a difficult task at best!). Plus, it can take advantage of the scodger/know variant of waiting before the first meeting, which I can't see it being of use to the 100 cycle day variants. Granted, it is less likely to have a quick resolution...
Anyone have a valid third solution that doesn't require 'cheating' by seeing the light while in solitary confinement? (I like the idea of having the meeting in the living room!)
|
|
IP Logged |
|
|
|
dabicho
Newbie
Posts: 1
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #21 on: Jul 25th, 2002, 3:26pm » |
|
My solution.
one leader.
The leader toggles each time he enters, except if its different than the last time he entered.
Others, toggle first time, and dont toggle subsequent times.
Then... then what?
I think im on the right trail but...
heeeeelp!
(besides my work, the best nice solution ive read so far was the meeting at the living room  )
|
|
IP Logged |
|
|
|
sjbrown
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #22 on: Jul 25th, 2002, 7:09pm » |
|
I think I've found another solution. (the only other two so far were the "Leader" solution and the one where it's off on the 101st (or 201st or 301st ...) day. )
100-day Months
Pretend every month has 100 days. Each prisoner is assigned a day of the month. You only switch on the light if you're in the room on your day, otherwise you switch the light off. If the light is on when you go in the room, you know prisoner d has been in the room. When you've seen the light on on *every* day of the month, you know every prisoner has been in the room.
badabing.DOT
|
|
IP Logged |
|
|
|
dj
Guest
|
 |
Re: How to Solve 100 prisoners & Light bulb?
« Reply #23 on: Jul 25th, 2002, 9:05pm » |
|
I assume
(1) The prisoners get together once at the beginning
(2) They can see the light from their cells
(3) You only get to toggle once per visit to the room
Solution:
If you enter the room for the first time, toggle the switch.
If you enter it again, don't do anything.
From your cell, count the toggles (on-to-off or off-to-on). That's how many prisoners have been there at least once. If yours would be the 100th toggle, everyone has been there.
|
|
IP Logged |
|
|
|
italic
Guest
|
|
Re: How to Solve 100 prisoners & Light bulb?
« Reply #24 on: Jul 25th, 2002, 9:55pm » |
|
could someone please post the solution? I am of the opinion it has to be one of the two following possibilities:
(1) - the one leader who counts each unique toggle. this would take a long, long time statistically, but this is most likely the best bet.
(2) - The night of the meeting is held in the main room, so the first person picked can assert they have all been there. I hate this idea (as it doesn't say anywhere that they meet anywhere specific) but I am slowly starting to wonder if this isn't the answer.
You can play around with binary counting all you want, but you need to have 1 person in charge for those toggles to mean anything.
Please, someone post the solution. or at least email it to me. it's driving me crazy!
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Notify of replies
Send Topic
Print