Author |
Topic: 100 prisoners & a light bulb (Read 166684 times) |
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 7526
|
 |
Re: 100 prisoners & a light bulb
« Reply #575 on: Jan 3rd, 2008, 4:39am » |
|
Various out-of-the-box solutions have been proposed, shards of glass, scratching marks on the wall, unscrewing the light bulb in small increments, defecating, bribing the guards, etc.
|
|
 IP Logged |
|
|
|
Random Lack of Squiggily Lines
Senior Riddler
Everything before 7/1/2008 is now irrelevant.
Gender:
Posts: 460
|
|
Re: 100 prisoners & a light bulb
« Reply #576 on: Jan 4th, 2008, 5:56am » |
|
i think most people are forgetting that the problem is about, 100 pecies of info, and 1 two state transmittor, the 100 have to know that the other 99 of them have been to this "Place"
it is only worded that way to make it more realistic.
Just given you a reality check
|
|
IP Logged |
You can only believe i what you can prove, and since you have nothing proven to cmpare to, you can believe in nothing.
I have ~50 posts to hack a "R" into a "D". Which one?
|
|
|
Ghost Sniper
Senior Riddler
Do not hide. It is useless.
Gender:
Posts: 599
|
|
Re: 100 prisoners & a light bulb
« Reply #577 on: Jan 4th, 2008, 6:33am » |
|
I believe that the problem with this riddle is that it can be interpreted in too many different ways. For example, can the walls be marked or not? Can you use anything from the room as a marker? and so on, and so on. The only way we will be able to get a completely correct answer is if the riddle is VERY specific on what is allowed and what is not.
|
|
IP Logged |
*sob* I miss my mommy... *blows nose* huh, I'm on? oh right.
(thinks to self) Time for my speech to these college kids.
"Reason is more important than all emotions..."
|
|
|
Paul Hammond
Newbie
Posts: 29
|
|
Re: 100 prisoners & a light bulb
« Reply #578 on: Jan 4th, 2008, 11:34am » |
|
It's easy enough to restate the puzzle so that you avoid all the "leave something in the room" answers. Something like:
100 prisoners are imprisoned in separate windowless, soundproof, smellproof etc. cells. Once a day the warden randomly chooses one of the prisoners and visits his cell. The prisoner is allowed to say to the warden either "on" or "off", after the warden has told him which of the two words yesterday's prisoner said.
The prisoners are allowed to meet up before to discuss their strategy... etc. etc.
They never have to visit some room with a lightbulb in it.
|
|
IP Logged |
|
|
|
Tedp20
Newbie
Posts: 1
|
|
Re: 100 prisoners & a light bulb
« Reply #579 on: Jan 4th, 2008, 1:54pm » |
|
If you think too hard about the problem, it seems that it just gives you a headache. Think in simple terms guys.
---
100 prisoners are imprisoned in solitary cells. Each cell is windowless and soundproof. There's a central living room with one light bulb; the bulb is initially off. No prisoner can see the light bulb from his or her own cell. Each day, the warden picks a prisoner equally at random, and that prisoner visits the central living room; at the end of the day the prisoner is returned to his cell. While in the living room, the prisoner can toggle the bulb if he or she wishes. Also, the prisoner has the option of asserting the claim that all 100 prisoners have been to the living room. If this assertion is false (that is, some prisoners still haven't been to the living room), all 100 prisoners will be shot for their stupidity. However, if it is indeed true, all prisoners are set free and inducted into MENSA, since the world can always use more smart people. Thus, the assertion should only be made if the prisoner is 100% certain of its validity.
Before this whole procedure begins, the prisoners are allowed to get together in the courtyard to discuss a plan. What is the optimal plan they can agree on, so that eventually, someone will make a correct assertion?
--
If during the preliminary meeting, the prisoners agree to only toggle the switch at a specific time during the day, they can safely assume that there is a prisoner in the courtyard. The prisoners cannot see the courtyard, and they cannot see the light bulb, but that doesnt mean they cannot see the light emitted from the light bulb. So therefore, if each prisoner agrees to only toggle the switch connected to the light bulb as long as they have not previously been allowed into the courtyard, they can safely say that on the 100th toggle, each prisoner has been in the courtyard at least once.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2872
|
|
Re: 100 prisoners & a light bulb
« Reply #580 on: Jan 5th, 2008, 2:58pm » |
|
on Jan 4th, 2008, 1:54pm, Tedp20 wrote:If you think too hard about the problem, it seems that it just gives you a headache. Think in simple terms guys.
---
100 prisoners are imprisoned in solitary cells. Each cell is windowless and soundproof. There's a central living room with one light bulb; the bulb is initially off. No prisoner can see the light bulb from his or her own cell. Each day, the warden picks a prisoner equally at random, and that prisoner visits the central living room; at the end of the day the prisoner is returned to his cell. While in the living room, the prisoner can toggle the bulb if he or she wishes. Also, the prisoner has the option of asserting the claim that all 100 prisoners have been to the living room. If this assertion is false (that is, some prisoners still haven't been to the living room), all 100 prisoners will be shot for their stupidity. However, if it is indeed true, all prisoners are set free and inducted into MENSA, since the world can always use more smart people. Thus, the assertion should only be made if the prisoner is 100% certain of its validity.
Before this whole procedure begins, the prisoners are allowed to get together in the courtyard to discuss a plan. What is the optimal plan they can agree on, so that eventually, someone will make a correct assertion?
--
If during the preliminary meeting, the prisoners agree to only toggle the switch at a specific time during the day, they can safely assume that there is a prisoner in the courtyard. The prisoners cannot see the courtyard, and they cannot see the light bulb, but that doesnt mean they cannot see the light emitted from the light bulb. So therefore, if each prisoner agrees to only toggle the switch connected to the light bulb as long as they have not previously been allowed into the courtyard, they can safely say that on the 100th toggle, each prisoner has been in the courtyard at least once.
|
|
For starters, the bulb's not in the courtyard - they meet in the courtyard to avoid them all visiting the living room before they start...
Secondly, seeing the light from their "windowless and soundproof" cells is gonna be tricky...
|
|
IP Logged |
|
|
|
alien2
Uberpuzzler
Gender:
Posts: 6986
|
|
Re: 100 prisoners & a light bulb
« Reply #581 on: Jan 11th, 2008, 8:20am » |
|
Quote:| Also, the prisoner has the option of asserting the claim that all 100 prisoners have been to the living room. |
|
If this isn't a new prison, rather an old one, although reconstructed to a higher standard, then at the very beginning of the whole procedure, 1st prisoner can make the assertion. Of course, I'm talking about previous 100 prisoners, which all had access to the central living room. 
|
|
IP Logged |
|
|
|
alien2
Uberpuzzler
Gender:
Posts: 6986
|
|
Re: 100 prisoners & a light bulb
« Reply #582 on: Jan 12th, 2008, 11:37am » |
|
One thing isn't quite clear to me. Should it be? The riddle states that there is one bulb in the central living room. But what does that mean, exactly? Does it mean that when the coiled-coil filament burns out, then it will be replaced with a new bulb? Or when it burns out, it will not be replaced at all? If the latter is the case, then perhaps considering the approximate duration of the bulb might be beneficial to prisoners. It probably won't help prisoners though, but it might clear up things a bit for riddlers. 
|
|
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 #583 on: Jan 12th, 2008, 12:53pm » |
|
It's an LED bulb, with theoretically unlimited lifetime. And the switch and wiring are also of exceptionally rugged design.
Indeed, our inmates would have been free from mechanical concerns had there not been a power outage on one day when the bulb was supposed to be on.
|
|
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
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: 100 prisoners & a light bulb
« Reply #584 on: Jan 12th, 2008, 3:06pm » |
|
When the lamp burns out, the position of the switch is enough to carry the information.
I am assuming a classical 2-position switch.
|
|
IP Logged |
|
|
|
alien2
Uberpuzzler
Gender:
Posts: 6986
|
|
Re: 100 prisoners & a light bulb
« Reply #585 on: Jan 16th, 2008, 1:43pm » |
|
Will someone finally solve this prison riddle in the name of Christ and Virgin Mary!
|
|
IP Logged |
|
|
|
Ghost Sniper
Senior Riddler
Do not hide. It is useless.
Gender:
Posts: 599
|
|
Re: 100 prisoners & a light bulb
« Reply #586 on: Jan 16th, 2008, 2:19pm » |
|
The only problem, Icey, is that not even Wu knows the intended answer. So even if he shows up, he is not going to be able to help us, and that includes clues. 
FOR GOODNESS SAKE, WE HAVE TO FIND WHO WROTE THIS RIDDLE!
edit:
Yoiks, I just found this:
http://www.ocf.berkeley.edu/~wwu/papers/100prisonersLightBulb.pdf
edit 2:
So many people refer back to the riddles site when talking about this riddle. It almost makes it seem as if Wu wrote the riddle.
|
| « Last Edit: Jan 16th, 2008, 2:24pm by Ghost Sniper » |
IP Logged |
*sob* I miss my mommy... *blows nose* huh, I'm on? oh right.
(thinks to self) Time for my speech to these college kids.
"Reason is more important than all emotions..."
|
|
|
Paul Hammond
Newbie
Posts: 29
|
|
Re: 100 prisoners & a light bulb
« Reply #587 on: Jan 17th, 2008, 6:22am » |
|
I think William Wu has actually said, possibly in this very thread, that his intended solution was the "single leader" solution with preliminary "snowball" round.
I think what happened is that this puzzle arose out of a possibly unintentional but crucial variation on the original IBM "23 prisoners" puzzle. In that puzzle, the warden visits at arbitrary intervals, not once per day, so any solution that makes use of the day number won't work. It is difficult to see how you could have multiple counters, snowball phases, or anything other than "token passing" in those circumstances, so for that puzzle Single Leader may be optimal.
Having the warden visit once per day doesn't sound like it would make much difference but, as we have discovered, it does.
|
| « Last Edit: Jan 17th, 2008, 6:23am by Paul Hammond » |
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: 100 prisoners & a light bulb
« Reply #588 on: Jan 17th, 2008, 6:50am » |
|
on Jan 17th, 2008, 6:22am, Paul Hammond wrote:| so for that puzzle Single Leader may be optimal. |
|
Although I can't find the paper at the moment, I believe the single leader solution to the IBM version has indeed been proven optimal.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
alien2
Uberpuzzler
Gender:
Posts: 6986
|
|
Re: 100 prisoners & a light bulb
« Reply #589 on: Jan 17th, 2008, 8:15am » |
|
on Jan 17th, 2008, 6:50am, SMQ wrote:
Although I can't find the paper at the moment, I believe the single leader solution to the IBM version has indeed been proven optimal. |
|
I second that, even though I'm not that good at these kinds of riddles. The single leader solution makes perfect sense to me.
|
|
IP Logged |
|
|
|
Paul Hammond
Newbie
Posts: 29
|
|
Re: 100 prisoners & a light bulb
« Reply #590 on: Jan 17th, 2008, 9:26am » |
|
on Jan 17th, 2008, 6:50am, SMQ wrote:
Although I can't find the paper at the moment, I believe the single leader solution to the IBM version has indeed been proven optimal.
--SMQ |
|
You could imagine a scenario in which the prisoners simply guess the rate at which the warden will visit the cell, and use some kind of staged scheme based on that. If the warden does in fact visit at roughly that rate, their scheme could work out faster than Single Leader would have done.
Of course, we have to assume that the warden could visit at a rate of a billion times a second, or only once per trillion millennia, with equal probability, so the probability that their guess will be usefully close to being correct approaches zero  . Whereas the single leader scheme doesn't care how often he visits.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2872
|
|
Re: 100 prisoners & a light bulb
« Reply #591 on: Jan 17th, 2008, 12:24pm » |
|
on Jan 17th, 2008, 9:26am, Paul Hammond wrote:
You could imagine a scenario in which the prisoners simply guess the rate at which the warden will visit the cell, and use some kind of staged scheme based on that. If the warden does in fact visit at roughly that rate, their scheme could work out faster than Single Leader would have done.
Of course, we have to assume that the warden could visit at a rate of a billion times a second, or only once per trillion millennia, with equal probability, so the probability that their guess will be usefully close to being correct approaches zero . Whereas the single leader scheme doesn't care how often he visits. |
|
The problem with any staged system with unknown intervals between visits is how you handle transitions between stages - neither of the two prisoners on either side of a stage boundary can know they are on either side of the boundary, and it's also possible for one or more stages to pass without anyone visiting - so even if you find a scheme that compensated for one stage transition, it could still fall apart when carried out across multiple stages...
|
|
IP Logged |
|
|
|
alien2
Uberpuzzler
Gender:
Posts: 6986
|
|
Re: 100 prisoners & a light bulb
« Reply #592 on: Mar 20th, 2008, 3:53pm » |
|
The 1st prisoner unscrews the bulb and puts it in particular corner, as previously agreed amongst the prisoners in the courtyard. And every time a prisoner is 1st time in the above room, he simply moves it a bit clockwise along the walls. In fact, the bulb will act like mechanical hand does, pretty much.
This might yield enough information to make the proper assertion. 
|
| « Last Edit: Mar 20th, 2008, 4:00pm by alien2 » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 100 prisoners & a light bulb
« Reply #593 on: Mar 21st, 2008, 1:02am » |
|
The topic is not dead, actually I was thinking about it in the small amount of free time I had last two days. But please don't spam it with out of box posts.
What I am thinking about is a combination of observers stop and Rezyk phase switch cost reduction method.
The cost will be that there will be dedicated prisoner not sending his token in binary phases and each upward superphase will end in one level lower than previous (the tokens of nondedicated prisoner will be split in the top phase and observers should ignore the information above this level). Downward superphases after the first one can be discarded at all.
After several superphases this will end at two level scheme.
Actually this changes the main streem of the algorithm only very little, but the cost of phase switches during error recovery is reduced.
Whether it leads to higher average time or smaller will be left to experiment. I expect only small difference which may be hard to notice.
|
| « Last Edit: Mar 23rd, 2008, 6:03am by Hippo » |
IP Logged |
|
|
|
Random Lack of Squiggily Lines
Senior Riddler
Everything before 7/1/2008 is now irrelevant.
Gender:
Posts: 460
|
|
Re: 100 prisoners & a light bulb
« Reply #594 on: Mar 22nd, 2008, 8:21am » |
|
wouldnt a light bulb burn out in ~27 years?
|
|
IP Logged |
You can only believe i what you can prove, and since you have nothing proven to cmpare to, you can believe in nothing.
I have ~50 posts to hack a "R" into a "D". Which one?
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 100 prisoners & a light bulb
« Reply #595 on: Mar 22nd, 2008, 8:39am » |
|
on Mar 22nd, 2008, 8:21am, Master of Everything 42 wrote:| wouldnt a light bulb burn out in ~27 years? |
|
I think there is still a lightbulb made by edison himself burning somewhere. The life expectancy is much lower though; but there's exceptions. And the lightbulb is irrelevant here anyway, as long as the switch has distinguishable states.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
alien2
Uberpuzzler
Gender:
Posts: 6986
|
|
Re: 100 prisoners & a light bulb
« Reply #596 on: Mar 22nd, 2008, 9:35am » |
|
on Mar 22nd, 2008, 8:21am, Master of Everything 42 wrote:| wouldnt a light bulb burn out in ~27 years? |
|
Prisoners will burn out in 27 years.
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: 100 prisoners & a light bulb
« Reply #597 on: Mar 22nd, 2008, 6:39pm » |
|
on Mar 22nd, 2008, 8:39am, towr wrote:| I think there is still a lightbulb made by edison himself burning somewhere. |
|
Yep, been burning for over 100 years at a fire station in Livermore, California.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 100 prisoners & a light bulb
« Reply #598 on: Mar 23rd, 2008, 6:02am » |
|
I have just run an experiment which should compare the algorithm with counnters on level 0 and observers on binary levels above it, where in 1st case the levels on binary phases are in /\///////... shape and in the other in /\/\/\/\... shape.
So I compare only cases when /\/ didn't terminate yet. And the /\//// shape for this sample is about 130 days faster
(currently 6647/6785).
This sample is around 1/40 of all cases so this improves the average by more than 3 days.
... I will probably implement the binary phases reduction mentioned recently ...
I cannot realy estimate whether this beats the 2 phases counters or not.
Hmm I became a bit sceptic. ... the combination of observers and crown ... if some binary counter fails and crown gathers half the badges the observers take almost no info so not to send the badge as a crown disqualify observers. On the other side if crown sends the badge the counter phase takes longer as the crown starts from zero. I will probably let the crown act as other badge owners during the initial top binary phase. After that the crown will start acting usually from zero. Choice of crown can be done as the prisoner taking tokens in the first snowball. Making rather big goal at the first snowball actually prevents the crown from loosing his badges at the top binary phase. We can choose in other way, but this seems to preserve maximal probability it gathers some badges. In the binary phases under top crown can deny sending his badge and he can gather badge to round his badges on this level to even number. ... this is rather frustrating you intend to gather almost all badges outside the crown hands during initial binary up and down to be observers well informed, but in the following up phases you do everything to collect all badges in the crown hands. Each decission has unpredictable consequences. One strategy for crown may be to collect badges (to even them) only in last say 150 days of each binary upward phase.
And collect all during downward phases. This highly increases probability that another prisoner lights the bulb on the topmost binary phase ... so observers will be well informed and the crown neednot loose his badges on the top level....
Ohh ... new fresh idea:
For the first top binary phase crown can act as all other badge owners until say last 150 days of the phase when it switches strategy to crown ... collecting badges at all costs. Observers didn't stop the top binary phase when they see on/off swith ... there is no reason for that as if this unions last two binary tokens the badge holder declares victory himself.
Observers only get info "At least half binary tokens entered the top level." whenever they see switch on during the phase.
This makes all observers well informed. And probability the crown gets more than half of all badges during the binary up phases is very high (with his passivity until last say 150 days during upward binary phases). ... I became a bit more optimistic
So the experiment was run ... first parametrisation gives result worse by 200 days [edit] it was actually around 500 days[/edit] this is probably caused by wrong spread of info during downward binary phases. I would probably change the strategy once more ... crown will act as a binary on the initial up phases and in the first part of top phase as well as in the first part of downward phases. Observers shouldnot gather info in the second part of the downward phases.
The last improvement gives around 3740 for current parametrisation so observers without crown are better so far.
But the mutation of parameters is a slow process so we may be surprised later (only if the original choise was very very bad).
|
| « Last Edit: Mar 24th, 2008, 2:27pm by Hippo » |
IP Logged |
|
|
|
Random Lack of Squiggily Lines
Senior Riddler
Everything before 7/1/2008 is now irrelevant.
Gender:
Posts: 460
|
|
Re: 100 prisoners & a light bulb
« Reply #599 on: Mar 24th, 2008, 6:26am » |
|
It's 4-watt too.
|
|
IP Logged |
You can only believe i what you can prove, and since you have nothing proven to cmpare to, you can believe in nothing.
I have ~50 posts to hack a "R" into a "D". Which one?
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Notify of replies
Send Topic
Print