Author |
Topic: 100 prisoners & a light bulb (Read 166673 times) |
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender: 
Posts: 4863
|
 |
Re: 100 prisoners & a light bulb
« Reply #500 on: Nov 15th, 2006, 6:32pm » |
|
Not just one answer - numerous answers. For "in the box" solutions (which are the most interesting for this puzzle), you can find a linked history of solutions here, and a full summary of the solutions up to that time here.
In the next 2 or 3 pages from the summary are several posts that improved upon the times reported in the summary by tweaking gypo's method mentioned in it. But the improvement was modest.
|
|
 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
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: 100 prisoners & a light bulb
« Reply #501 on: Nov 15th, 2006, 7:50pm » |
|
on Nov 15th, 2006, 6:32pm, Icarus wrote:| ...the improvement was modest. |
|
Oh. Come. On. Leonid and I squeezed a further 29 days out of that algorithm! That's almost a 1% improvement!
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
flamingdragon
Uberpuzzler
Gender:
Posts: 671
|
|
Re: 100 prisoners & a light bulb
« Reply #502 on: Nov 16th, 2006, 3:40pm » |
|
Those are very confusing and complicated, has this one been said yet and would it work:
Screw the bulb. Get each prisoner to make a mark on the wall with his fingernail the first time he enters the room. When there are 100 marks, all of them have been there.
|
|
IP Logged |
"The fool doth think he is wise, yet the wise man knoweth himself to be a fool"
"He who commands the past, commands the future. He who commands the future, commands the past."
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: 100 prisoners & a light bulb
« Reply #503 on: Nov 16th, 2006, 5:14pm » |
|
Only about 50 to 100 times.
|
|
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
|
|
|
flamingdragon
Uberpuzzler
Gender:
Posts: 671
|
|
Re: 100 prisoners & a light bulb
« Reply #504 on: Nov 16th, 2006, 8:10pm » |
|
So would that be a correct answer?
|
|
IP Logged |
"The fool doth think he is wise, yet the wise man knoweth himself to be a fool"
"He who commands the past, commands the future. He who commands the future, commands the past."
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 100 prisoners & a light bulb
« Reply #505 on: Nov 17th, 2006, 1:13am » |
|
on Nov 16th, 2006, 8:10pm, flamingdragon wrote:| So would that be a correct answer? |
|
Well, the room gets painted every so often (every 'public' building has regular maintenance after all). So there's no guarantee that even if they are all brought into the room infinitely often that they'll ever know with certainty that they have all been in there. (For example, prisoner X might only be shown into the room at times just before it's repainted. So the others will never see his mark)
Also, it goes past the intention of the puzzle; but that's never stopped anyone here before
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: 100 prisoners & a light bulb
« Reply #506 on: Nov 17th, 2006, 1:54am » |
|
Let every prisonner grab the light bulb with the right hand when entering the room. When there are 500 fingerprints on the bulb (not counting duplicates), everybody was there.
|
|
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 #507 on: Nov 17th, 2006, 7:30pm » |
|
The warden put some effort into setting up this "communicate only by the light" scenario, and has only promised not to interfere with that means. I wouldn't put it past him to clean the room between visits - or worse yet, add marks of his own. 
We've accepted that the "leave a mark" solution is valid before, but frankly, it isn't interesting: you don't get any insight from it.
While the best "in-the-box" solutions (those that communicate only by the state of the light) are quite complex, others are fairly simple:
(1) Complete cycle scheme: break the days into "cycles" of 100 days each. At the beginning of each cycle, the first prisoner makes sure the light is on. Any time someone visits for the second time in a cycle, they turn the light off. If the last visitor of the cycle finds the light on, he knows that everyone must have visited that cycle and declares. This method works, but is extremely slow - taking much longer than the expected lifetime of the universe to finish on average.
(2) Distribution scheme: This one also uses 100-day cycles. Each day of a cycle is numbered from 1-100, and each prisoner is also assigned a number. A prisoner visiting on day N can only turn on (or leave on) the light if he knows that prisoner N has visited. If a prisoner visiting on day N+1 (or day 1 if N =100) finds the light on, he knows that prisoner N has visited. When one of the prisoners learns that all others have visited the room, he declares. This scheme on average takes about 8300 years to complete.
(3) Single Leader scheme: At the meeting, one prisoner is picked as leader. Only the leader is allowed to turn off the light. Everyone else may turn the light on only once, which they will do at the first opportunity. The leader keeps a count - starting at 1, for himself - of the number of times he turns off the light. When it reaches 100, he declares. This method takes a far more reasonable 28.5 years on average to complete.
(4) Single Leader with "snowball round": this was the solution that William Wu had in mind when he posted this riddle. This runs like the single leader solution, but the leader is not picked at the initial meeting. Instead, the first 100 days is set aside as special. The first guy in turns on the light. Everyone who comes in during those first 100 days and finds the light on also considers themselves to have turned on the light. The first guy to come in a second time (on day N) turns off the light and becomes the leader. He starts his count at N-1, since that many prisoners (including himself) have already visited. Anyone coming in during the first 100 days and finding the light off does not turn it on or do anything else. After the 100 days are over, the rules of the single leader method take effect. This shaves about 3 years off the straight single leader method, taking about 25.6 years on average.
The best time so far is about 9.5 years, set by Leonid Broukhis and the ever-humble SMQ.
|
|
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
|
|
|
flamingdragon
Uberpuzzler
Gender:
Posts: 671
|
|
Re: 100 prisoners & a light bulb
« Reply #508 on: Nov 19th, 2006, 5:35pm » |
|
on Nov 17th, 2006, 1:54am, Grimbal wrote:Let every prisonner grab the light bulb with the right hand when entering the room. When there are 500 fingerprints on the bulb (not counting duplicates), everybody was there.
|
|
I'm pretty sure the light bulb isn't big enough to see all the 100 fingerprints and I doubt they are allowed to use finger print detecting equipment or anything, except one thing which just gave me a solution, thanks.
Most likely the prisoners have clothes, so when they get into the room they take off their shirts and throw them the ground, when there are 100 shirts on the ground, the person can declare everyone has been there. 
Of course it is essentialy the same as marking in the wall, only more likely to happen since the wall probably isn't markable.
|
| « Last Edit: Nov 19th, 2006, 5:37pm by flamingdragon » |
IP Logged |
"The fool doth think he is wise, yet the wise man knoweth himself to be a fool"
"He who commands the past, commands the future. He who commands the future, commands the past."
|
|
|
rmsgrey
Uberpuzzler
   
Gender:
Posts: 2872
|
|
Re: 100 prisoners & a light bulb
« Reply #509 on: Nov 20th, 2006, 7:24pm » |
|
on Nov 19th, 2006, 5:35pm, flamingdragon wrote:
I'm pretty sure the light bulb isn't big enough to see all the 100 fingerprints and I doubt they are allowed to use finger print detecting equipment or anything, except one thing which just gave me a solution, thanks.
Most likely the prisoners have clothes, so when they get into the room they take off their shirts and throw them the ground, when there are 100 shirts on the ground, the person can declare everyone has been there.
Of course it is essentialy the same as marking in the wall, only more likely to happen since the wall probably isn't markable. |
|
I think someone already suggested that with some other item of clothing...
|
|
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 #510 on: Nov 21st, 2006, 4:15pm » |
|
Fingerprints, shirts, marks on the wall, piles of *&^# in the corner, turning the bulb ... all of these have been suggested, and it is very easy to come up with other variations. But all of them assume that the warden or other personel will do nothing to interfere, which is in no way indicated in the puzzle.
On the other hand, the warden has effectively promised not to change the on/off state of the light bulb - making this the only sure means of communication. (As sure as the warden is trustworthy - but if he isn't, then you don't have a riddle.)
|
|
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
|
|
|
flamingdragon
Uberpuzzler
Gender:
Posts: 671
|
|
Re: 100 prisoners & a light bulb
« Reply #511 on: Nov 25th, 2006, 6:38pm » |
|
on Nov 21st, 2006, 4:15pm, Icarus wrote:Fingerprints, shirts, marks on the wall, piles of *&^# in the corner, turning the bulb ... all of these have been suggested, and it is very easy to come up with other variations. But all of them assume that the warden or other personel will do nothing to interfere, which is in no way indicated in the puzzle.
On the other hand, the warden has effectively promised not to change the on/off state of the light bulb - making this the only sure means of communication. (As sure as the warden is trustworthy - but if he isn't, then you don't have a riddle.) |
|
He doesn't say he will interfere with anything else either, and exactly, u don't know if he's trustworthy. Therefore both kinds of answers are equally valid.
|
|
IP Logged |
"The fool doth think he is wise, yet the wise man knoweth himself to be a fool"
"He who commands the past, commands the future. He who commands the future, commands the past."
|
|
|
Three Hands
Uberpuzzler
Gender:
Posts: 715
|
|
Re: 100 prisoners & a light bulb
« Reply #512 on: Nov 26th, 2006, 5:10am » |
|
Granted, both kinds of answer are valid. However, one kind poses a significantly greater challenge to find and prove a "best possible" answer - there are several variations on the "think outside the box, mark the room/bulb in some way that demonstrates you have been there on that occasion...", and after a while these become dull - sometimes imaginative, but dull. This thread already has several examples of that kind of solution, and I believe has been acknowledged as a reasonable solution on various occasions.
However, by trying to solve the puzzle that is intended to be the one presented, there is a far greater challenge to your logical/mathematical ability and being able to spot workable methods. As has already been shown, several different types of solution are possible, and some are expected to work faster than others. While it is clever in one respect to come up with a "fingerprints, shirts, marks on the wall" etc. type solution, it is clever in a different respect to come up with a solution to the intended problem - and even more clever to refine such a solution to the level it is at currently. I never really got past the "leader" method in my attempts, and I doubt I'd know where to start on improving on current methods.
Similar applies to a lot of the other puzzles on the forums. Although attacking the wording is a useful tool to use when looking for solutions (trust me, having done a philosophy degree, I know all about attacking wordings ) there comes a point where the spirit/intention of the puzzle should be recognised, and different methods of problem-solving begin. Most, if not all, of the board regulars tend to accept that there may be multiple solutions for riddles beyond the "intended answer", but sometimes it's worth trying to find that "intended answer". If the riddle is well designed, that answer will feel like it fits better than others.
Apologies for the rant, just felt it might help...
|
|
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 #513 on: Nov 26th, 2006, 11:46am » |
|
on Nov 25th, 2006, 6:38pm, flamingdragon wrote:| He doesn't say he will interfere with anything else either, and exactly, u don't know if he's trustworthy. Therefore both kinds of answers are equally valid. |
|
By that reasoning, the answer "They don't have to do anything, because tomorrow Godzilla will come by, tear off the roof, and eat the warden" is also a valid answer, since the riddle doesn't mention that Godzilla won't.
Because the warden has not said he won't interfere with other means of communication, you are taking a risk by assuming he doesn't. The common understanding for this riddle is that the prisoners do not declare until they are 100% sure that everyone has visited. This is never the case if the communication depends on a means with which the warden is free to interfere.
As for the warden's trustworthiness - the idea that the warden cannot be trusted to follow his word does not make other answers equally valid. What it does is make the entire riddle invalid, as there is no solution with an untrustworthy warden.
|
|
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
|
|
|
flamingdragon
Uberpuzzler
Gender:
Posts: 671
|
|
Re: 100 prisoners & a light bulb
« Reply #514 on: Nov 26th, 2006, 2:08pm » |
|
on Nov 26th, 2006, 11:46am, Icarus wrote:
By that reasoning, the answer "They don't have to do anything, because tomorrow Godzilla will come by, tear off the roof, and eat the warden" is also a valid answer, since the riddle doesn't mention that Godzilla won't.
Because the warden has not said he won't interfere with other means of communication, you are taking a risk by assuming he doesn't. The common understanding for this riddle is that the prisoners do not declare until they are 100% sure that everyone has visited. This is never the case if the communication depends on a means with which the warden is free to interfere.
As for the warden's trustworthiness - the idea that the warden cannot be trusted to follow his word does not make other answers equally valid. What it does is make the entire riddle invalid, as there is no solution with an untrustworthy warden. |
|
LOL, I love godzilla.
And that would not be a valid answer b/c the question is how can they be sure everyone has been in there, not how to escape.
And the wardens untrustworthiness wouldn't make the riddle invalid b/c it's just a % chance that the warden is untrustworthy, not a gurantee.
|
|
IP Logged |
"The fool doth think he is wise, yet the wise man knoweth himself to be a fool"
"He who commands the past, commands the future. He who commands the future, commands the past."
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: 100 prisoners & a light bulb
« Reply #515 on: Nov 26th, 2006, 5:47pm » |
|
But the prisoners do not declare until they are 100% sure that everyone has been there. If the warden is not trustworthy, they can never be 100% sure.
If you are wondering about the 100% business, it came about because someone pointed out early on that if the prisoners are willing to accept a little bit of risk, they could just wait a couple years and then declare with 95-98% certainty. While a valid point, it too becomes quickly uninteresting.
|
|
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
|
|
|
alien2
Uberpuzzler
Gender:
Posts: 6986
|
|
Re: 100 prisoners & a light bulb
« Reply #516 on: Nov 27th, 2006, 4:13pm » |
|
Somebody stop this riddle. I can't sleep nights.
|
|
IP Logged |
|
|
|
koonie32
Junior Member
Posts: 72
|
|
Re: 100 prisoners & a light bulb
« Reply #517 on: Dec 8th, 2006, 4:51pm » |
|
Lol the funny part is this meeting of the prisoners MUST be going on for a long time if they cant come up with an idea for 4 years lol.. (actually the topic has been longer than that).
|
|
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 #518 on: Dec 8th, 2006, 8:29pm » |
|
There have been numerous valid solutions posted in those 4 years. The thread keeps going because the question of how to get them out as fast as possible by "in-the-box" means is intriguing.
|
| « Last Edit: Dec 8th, 2006, 8:30pm by Icarus » |
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
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 100 prisoners & a light bulb
« Reply #519 on: Jan 12th, 2007, 12:25pm » |
|
It seemed to me, the post lenght is limited, so I should divide my initial post to several parts...
Hi, I had known modified problem without knowledge of the visit count. Only the one leader solution seemed to be possible. (Without knowing the initial state, there was small complication ... either
A) counter becames "switcher" and drone can light the bulb only once but only when he have seen it on before.
or
B) drone can light the bulb twice and counter swithes it off 198 times.
Your version of the problem is very interesting ... the optimisation dimension for this random process ...
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 100 prisoners & a light bulb
« Reply #520 on: Jan 12th, 2007, 12:32pm » |
|
I have made some progress before reading whole this thread. There is one optimisation which seems noone have used in the full strenght.
The observers can stop the process. This is especially powerfull when the final stages of the process are binary. The goal is to know that all the initial tokens for the binary stage were created.
Tokens neednot be collected. Each prisoner can maintain a list li. li is the number of tokens that surely left the i-th binary stage. The numbers li are related (li>=2li+1, having a token in stage i+1 means li>=2).
In the top binary stage when the light is on every observer knows half of the tokens left previous levels.
In this observer end approach, it seems to be better to take downward order of phases after initial upward order.
(In stage when token represents 1/4 of tokens, when the light is on, every visitor who knows 1/2 of tokens left stage already receives information that 3/4 of tokens left previous stages ...)
It's very probable that in the stage on level that failed in initial run or in following upward binary stage an informed visitor is found.
... improving the algorithm robustness.
|
| « Last Edit: Nov 26th, 2008, 1:50pm by Hippo » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 100 prisoners & a light bulb
« Reply #521 on: Jan 12th, 2007, 12:42pm » |
|
I have run genetic algorithm to find optimal parameters for such a process ... no snowroll and dynamic counter selection vere used yet ...
The most successful "gen" was ... the 16 counters in initial stage followed by binary levels with stage/phase lengths 1/1922, 8/473, 16/416, 32/421, 64/336, 32/187, 16/320, 8/320, 1/320, 8/320, 16/320, 32/320, 64/320, 32/320, ... 67328 attempts gives the average 3583.12.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 100 prisoners & a light bulb
« Reply #522 on: Jan 12th, 2007, 12:44pm » |
|
I am thinking about incorporating initial snowroll phase and better counter selection. I am also thinking about 12 counters with 2-2-3 phases, but it seems to me the visitors method for ternary phase is very unstable.
I suppose the initial snowroll phase and the optimized counter selection can save several tens of days. ... I will work on it next week. ... hoping to break 3400 barrier
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 100 prisoners & a light bulb
« Reply #523 on: Jan 12th, 2007, 12:49pm » |
|
Analytic solutions seemed to be very complicated,
but it seemed to me that dynamic programming can be used successfully to improve choices of phase lengths. ... I hope after the week I will post much better tuned algorithm.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 100 prisoners & a light bulb
« Reply #524 on: Jan 13th, 2007, 1:12am » |
|
I have reread the best known algorithms sumarized on page 15. The Rezyk one is very nice approach as it ends with one infinit one counter phase ... which removes the bigest disadvantage of too many phases algorithms ... the high cost of phase switch.
I am not sure how the comparison with the any observer stop method will end but I hope my method is better .
(sending i+1 level token in rezyk requires 400 days in average so the downward phases take longer time...)
The initialisation in gypo's algorithm surely can be optimized. The penalty for getting two badges is rather high so one should optimize its probability.
Initial snowroll can be used either.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Notify of replies
Send Topic
Print