wu :: forums « wu :: forums - 100 prisoners & a light bulb » Welcome, Guest. Please Login or Register. Jan 21st, 2022, 3:42am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: towr, ThudnBlunder, Eigenray, Icarus, SMQ, Grimbal, william wu)    100 prisoners & a light bulb « Previous topic | Next topic »
 Pages: 1 ... 19 20 21 22 23  ...  25 Notify of replies Send Topic Print
 Author Topic: 100 prisoners & a light bulb  (Read 161155 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: 7517
 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.

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: 2844
 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: 6931
 Re: 100 prisoners & a light bulb   « Reply #516 on: Nov 27th, 2006, 4:13pm »

Somebody stop this riddle. I can't sleep nights.

* insomnia * Sleepless in Seattle *  poppies will make me sleep * will I dream, Hal? *
 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
 Pages: 1 ... 19 20 21 22 23  ...  25 Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »