wu :: forums « wu :: forums - 100 PRISONERS AND TWO LIGHT BULBS » Welcome, Guest. Please Login or Register. May 21st, 2024, 10:16pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: Eigenray, william wu, towr, SMQ, Grimbal, ThudnBlunder, Icarus)    100 PRISONERS AND TWO LIGHT BULBS « Previous topic | Next topic »
 Pages: 1 2 Reply Notify of replies Send Topic Print
 Author Topic: 100 PRISONERS AND TWO LIGHT BULBS  (Read 18083 times)
thrillseeker
Newbie

Posts: 22
 Re: 100 PRISONERS AND TWO LIGHT BULBS   « Reply #25 on: Sep 6th, 2005, 8:56pm » Quote Modify

I have found a solution online for the previous riddle..100 prisoners and a light bulb. The solution is clever. I have used this solution to create a solution for the riddle...100 prisoners and 2 light bulbs. I believe this will work. Keep in mind that the prisoners are not chosen in any order, only when the guard feels like sending one in.

The prisoners decide that a LEADER will be choosen. Lets say for example that Jason is the chosen leader.

When Jason is sent to the room for the first time, he pays no attention to the state of the bulbs, and from that point on, the counting begins. Jason leaves the room making sure that both lights are on and counts (1) for himself. No prisoner except Jason is allowed to turn the lights on.

When a prisoner besides Jason is sent to the room, he leaves the room with both lights off, and is allowed to do this only once. If a prisoner has been sent to the room a second time (or greater) he may not turn the lights off again because he already has once.

Every time that Jason enters the room and turns the lights on, he knows that a new prisoner has entered the room, because a prisoner who has never been to the room before is allowed only one time to turn the lights off.

When Jason has counted that he has turned the lights on 100 times, then he knows that all of the prisoners have taken a trip to the room.

This solution assumes that the warden will send the prisoners that went into the room BEFORE Jason, back to the room after Jason has entered for the first time.

This could take days or years depending on how long the warden decides to take before sending  prisoners into the room after Jasons first visit. He could do 50 a day or 1 a month. That is the main difference between this riddle and  the original riddle with one bulb. I believe with the one bulb riddle it could be completed in 1000 days because the prisoners are chosen one a day and equally. With that in mind, Jason would turn the light on once every 100 days and every prisoner would take a trip to the room after Jasons first visit because they are choosen one a day and equally.

There is probably and alternative solution because I did not use both bulbs seperately, but as one.
 IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7527
 Re: 100 PRISONERS AND TWO LIGHT BULBS   « Reply #26 on: Sep 7th, 2005, 2:22am » Quote Modify

Online? where?

By the way, it would take more than 10000 days on average, because near the end of the count, there are chances that none of the prisonners who have never been in the room enter the room before Jason enters the room again.
 « Last Edit: Sep 7th, 2005, 2:26am by Grimbal » IP Logged
rmsgrey
Uberpuzzler

Gender:
Posts: 2873
 Re: 100 PRISONERS AND TWO LIGHT BULBS   « Reply #27 on: Sep 7th, 2005, 4:57am » Quote Modify

on Sep 7th, 2005, 2:22am, Grimbal wrote:
 Online? where?   By the way, it would take more than 10000 days on average, because near the end of the count, there are chances that none of the prisonners who have never been in the room enter the room before Jason enters the room again.

There's also the problem of what happens if the bulbs are both on to start with - the first prisoner to go in (unless it's Jason) finds the bulbs on, assumes Jason has been in already, turns them off, and leaves them alone forevermore. When Jason reaches 99, his count stalls permanently because that first guy can never be counted...

Wasn't it this solution that was calculated at taking an average of 27 years (around 100,000 days) at 1 visit per day?
 IP Logged
thrillseeker
Newbie

Posts: 22
 Re: 100 PRISONERS AND TWO LIGHT BULBS   « Reply #28 on: Sep 7th, 2005, 9:07pm » Quote Modify

rmsgrey,

It does not matter if a prisoner goes into the room before jason and messes with the bulbs. Jason is the one doing the counting. So whatever happens to the bulbs before Jasons first visit is irrelevent. Jason does not count the state of the bulbs when he enters for the first time, he only counts one for himself and leaves the room with both bulbs on. Every time Jason goes into the room after that and the bulbs are off, he knows that a prisoner has made his first trip to the room. If a prisoner goes into the room on his first visit and finds the bulbs on, then he is the first prisoner on his first trip to enter the room after Jason has made a visit.

As I stated earlier the only problem that I can see with my solution is that there is no evidence that the warden will continue to send prisoners into the room after he has sent in the 100th. If the warden continues to send prisoners into the room after the 100th has gone in, that is the only way that the prisoners who entered the room before Jasons first visit can be accounted for.

For the 2 bulb riddle solution it would take more than 1000 days. I was saying that for the 1 bulb riddle solution it would take only 1000 days because Jason enters the room once every 100 days and when he enters, the bulbs will always be off. And now that I think about it, Jason has no need to count anything except the number of times that he has entered the room! Once he has entered 2 times, all of the 100 prisoners have made a visit.
 « Last Edit: Sep 8th, 2005, 1:08am by thrillseeker » IP Logged
thrillseeker
Newbie

Posts: 22
 Re: 100 PRISONERS AND TWO LIGHT BULBS   « Reply #29 on: Sep 7th, 2005, 9:32pm » Quote Modify

I went onto GOOGLE (the best search engine in our solar system) and typed this...100 prisoners light bulb

There are a number of sites that appear. Some with solutions, some without. I think this site has a fine solution.

http://www.physicsforums.com/archive/t-30021_5_Star_Logic_Problem_(100_prisoners_and_a_light_bulb).html

There was another site I found on another day, but I cannot seem to find it now
 IP Logged
rmsgrey
Uberpuzzler

Gender:
Posts: 2873
 Re: 100 PRISONERS AND TWO LIGHT BULBS   « Reply #30 on: Sep 8th, 2005, 4:33am » Quote Modify

on Sep 7th, 2005, 9:07pm, thrillseeker wrote:
 rmsgrey,           It does not matter if a prisoner goes into the room before jason and messes with the bulbs. Jason is the one doing the counting. So whatever happens to the bulbs before Jasons first visit is irrelevent. Jason does not count the state of the bulbs when he enters for the first time, he only counts one for himself and leaves the room with both bulbs on. Every time Jason goes into the room after that and the bulbs are off, he knows that a prisoner has made his first trip to the room. If a prisoner goes into the room on his first visit and finds the bulbs on, then he is the first prisoner on his first trip to enter the room after Jason has made a visit.     As I stated earlier the only problem that I can see with my solution is that there is no evidence that the warden will continue to send prisoners into the room after he has sent in the 100th. If the warden continues to send prisoners into the room after the 100th has gone in, that is the only way that the prisoners who entered the room before Jasons first visit can be accounted for.     For the 2 bulb riddle solution it would take more than 1000 days. I was saying that for the 1 bulb riddle solution it would take only 1000 days because Jason enters the room once every 100 days and when he enters, the bulbs will always be off. And now that I think about it, Jason has no need to count anything except the number of times that he has entered the room! Once he has entered 2 times, all of the 100 prisoners have made a visit.

So what does a prisoner do ifhe enters the room and finds both bulbs on on his first visit? What does he do on his next visit and subsequent visits?

How about if the prisoner finds both bulbs off on his first visit?

Or finds them in a mixed state?

A prisoner on his first visit can only tell whether Jason has already visited if he finds the bulbs in a mixed state. Otherwise, if he changes the bulbs, he has no way of knowing for sure that Jason will get his signal as Jason may not yet have visited.

If all 100 prisoners have to visit before any of them visit for a second time, then you don't need Jason - any prisoner visiting for the second time will do.

However, if the warden selects from all the prisoners uniformly at random each time rather than restricting himself to those who have visited fewer times, then you'd expect at least one prisoner to have visited at least twice in the first dozen or so visits (after 12 visits, the probability is 49.7%; after 13, 55.8%). I believe this site specifies random-with-replacement.
 IP Logged
thrillseeker
Newbie

Posts: 22
 Re: 100 PRISONERS AND TWO LIGHT BULBS   « Reply #31 on: Sep 8th, 2005, 8:55pm » Quote Modify

msgrey has stated the following:

So what does a prisoner do ifhe enters the room and finds both bulbs on on his first visit? What does he do on his next visit and subsequent visits?

How about if the prisoner finds both bulbs off on his first visit?

Or finds them in a mixed state?

A prisoner on his first visit can only tell whether Jason has already visited if he finds the bulbs in a mixed state. Otherwise, if he changes the bulbs, he has no way of knowing for sure that Jason will get his signal as Jason may not yet have visited.

If all 100 prisoners have to visit before any of them visit for a second time, then you don't need Jason - any prisoner visiting for the second time will do.

However, if the warden selects from all the prisoners uniformly at random each time rather than restricting himself to those who have visited fewer times, then you'd expect at least one prisoner to have visited at least twice in the first dozen or so visits (after 12 visits, the probability is 49.7%; after 13, 55.8%). I believe this site specifies random-with-replacement.

If a prisoner enters the room for his first time and the lights are on he turns them off. When that prisoner enters the room again he does nothing to the bulbs because when he turned them off in the past Jason accounted for that prisoners visit. When a prisoner enters the room for his first time and finds the light off, he does nothing to the lights, he leaves them alone. Prisoners never turn the lights on. Only Jason turns them on.

If a prisoner finds the bulbs in a mixed state, then he knows that Jason has never been to the room. Jason always leaves both lights on before he leaves. If a prisoner enters the room before Jasons first visit and finds the lights on he can turn them off and it will not affect Jasons count because Jason counts 1 for himself on his first visit. Every visit that Jason makes after that, he accounts for 1 prisoner, unless no prisoner on a first visit has entered the room since Jasons last visit. And Jason will know this if he enters the room and the lights are on. The warden sends prisoners in when he feels like it and in no order, so it is possible that between Jasons visits, only prisoners who have already been sent to the room were sent in.

You stated...."A prisoner on his first visit can only tell whether Jason has already visited if he finds the bulbs in a mixed state." No. That is not correct. The only way a prisoner can know if Jason has visited the room is if both lights are on. Jason never leaves the bulbs in a mixed state. Actually, it does not matter if the prisoner knows whether or not Jason has visited the room. He just turns the lights off if he finds them on and he will be accounted for.

You stated...."If all 100 prisoners have to visit before any of them visit for a second time, then you don't need Jason - any prisoner visiting for the second time will do."

This is true, assuming that the prisoners know that all 100 of the prisoners must visit before one visits twice. The riddle does not state either. It just says that the warden sends em in randomly, when he feels like it.

That is why that solution does not work for the 1 bulb riddle. If the prisoners knew that the warden sent in one per day and equally, then ya, the first prisoner to make his second visit can make the claim.

Im starting to think that this riddle is not solveable.
I have found a flaw in my solution.

If a prisoner enters the room before Jasons first visit and finds both lights on, he turns them off. That prisoner will not be accounted for because Jason does not start counting untill he makes his first visit into the room. The prisoner who entered before him and turned them off is not allowed to turn them off again on a future visit because all prisoners are told to turn the lights off only one time. DANG! I was so close. How can the prisoners that enter the room before Jason be accounted for?
 « Last Edit: Sep 8th, 2005, 8:57pm by thrillseeker » IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7527
 Re: 100 PRISONERS AND TWO LIGHT BULBS   « Reply #32 on: Sep 9th, 2005, 12:38am » Quote Modify

One easy fix is that each prisonner turns off the lights twice.  Jason can miss only one count.  When he found the light off 197 times (not counting his first visit) he knows 99 prisonners have been there.  98 prisonners could turn off the light only 196 times.

Of course, it will nearly double the waiting time.
 IP Logged
thrillseeker
Newbie

Posts: 22
 Re: 100 PRISONERS AND TWO LIGHT BULBS   « Reply #33 on: Sep 9th, 2005, 9:48am » Quote Modify

on Sep 9th, 2005, 12:38am, Grimbal wrote:
 One easy fix is that each prisonner turns off the lights twice.  Jason can miss only one count.  When he found the light off 197 times (not counting his first visit) he knows 99 prisonners have been there.  98 prisonners could turn off the light only 196 times.   Of course, it will nearly double the waiting time.

Then what happens if a prisoner is sent to the room before Jasons first visit and finds the lights off and is never sent back to the room? He will never have the opportunity to turn the lights off ever and cannot be accounted for.

There must be a way to use both bulbs to count prisoners that enter before Jasons first visit and after his first visit.
 IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7527
 Re: 100 PRISONERS AND TWO LIGHT BULBS   « Reply #34 on: Sep 10th, 2005, 4:06am » Quote Modify

That would mean the wardens are not fair.  We are assuming the prisonners are sent randomly.  Even if in theory it can happen that one prisonner never gets taken in again, the probability of it falls to 0%.

So the scheme can fail, but with probability 0%.  I'd say it is an acceptable risk.
 IP Logged
rmsgrey
Uberpuzzler

Gender:
Posts: 2873
 Re: 100 PRISONERS AND TWO LIGHT BULBS   « Reply #35 on: Sep 10th, 2005, 7:05am » Quote Modify

on Sep 9th, 2005, 9:48am, thrillseeker wrote:
 Then what happens if a prisoner is sent to the room before Jasons first visit and finds the lights off and is never sent back to the room? He will never have the opportunity to turn the lights off ever and cannot be accounted for.   There must be a way to use both bulbs to count prisoners that enter before Jasons first visit and after his first visit.

One way to describe a minimal condition to guarantee that a solution is possible is that (unless a prisoner claims victory) no prisoner will ever enter for the last time.
 IP Logged
thrillseeker
Newbie

Posts: 22
 Re: 100 PRISONERS AND TWO LIGHT BULBS   « Reply #36 on: Sep 12th, 2005, 7:26pm » Quote Modify

Ok, I have a new solution, maybe it is flawed but I cant see anything wrong with it. (Besides the fact that it would probably take forever.)

They name the bulbs. Bulb A, and Bulb B.

Only Jason is allowed to turn both bulbs off.

They decide that any prisoner who enters the room and finds both bulbs off, will turn them both on.

They decide that any prisoner who enters the room and finds both bulbs on, will leave bulb A on and Bulb B off.

They decide that any prisoner who enters the room and finds Bulb A on and Bulb B off, will switch Bulb A off and Bulb B on.

They decide that any prisoner who enters the room and finds Bulb A off and Bulb B on can do nothing.

All prisoners must do this two times,  but must  make an adjustment identical to their last adjustment. (This is to insure that the first two prisoners sent in before Jasons first visit will not use up both of their adjustments before Jasons first visit.)

More than likely, a prisoner(s) will be sent to the room before Jason makes his first visit. Before he (they) leaves the room, he sets the bulbs accordingly.

Prisoners who were sent to the room before Jasons first visit and were allowed to adjust the bulbs can total only 3. ( Assuming the possibility that the very first prisoner to be sent to the room found both bulbs off.) All others will have to wait for a future date to adjust the bulbs and be accounted for.

When Jason enters the room for the first time, he ignores the state of the bulbs and turns both of them off.

Every time that Jason enters the room in the future, he checks the state of the bulbs and has the opportunity to account for THREE prisoners.

1. The prisoner who found both bulbs off.
2. The prisoner who found both bulbs on.
3. The prisoner who found Bulb A on and Bulb B off.

I believe  that when Jason counts 198 he may add two for himself and make the claim.

Its too bad that the prisoners dont know the original state of the bulbs. If they did, then Jason would know how many prisoners entered the room before his first visit and were allowed to adjust the bulbs. I cant see any way of accounting for those prisoners without having all the prisoners adjust the bulbs 2 times and making identical adjustments.
 « Last Edit: Sep 12th, 2005, 7:46pm by thrillseeker » IP Logged
jollytall
Senior Riddler

Gender:
Posts: 585
 Re: 100 PRISONERS AND TWO LIGHT BULBS   « Reply #37 on: Jan 24th, 2015, 12:01pm » Quote Modify

The above solutions use the fact that there are 2 bulbs, only to use a 2-bit rather than a 1-bit counter. Someone asked me to use the 2 bulb version where everybody must have the same strategy. To me this means that no Jason can be selected in advance.
I can solve it easily if the initial states are known or if there is a periodicity in the visits (the first visitor can set any initial state). The challenge I try to solve is:
- Symmetric solution (i.e. identical algorithm for all prisoners, no leader appointed upfront)
- Random timing
- Unknown initial state
 IP Logged
rmsgrey
Uberpuzzler

Gender:
Posts: 2873
 Re: 100 PRISONERS AND TWO LIGHT BULBS   « Reply #38 on: Jan 25th, 2015, 10:07am » Quote Modify

on Jan 24th, 2015, 12:01pm, jollytall wrote:
 The above solutions use the fact that there are 2 bulbs, only to use a 2-bit rather than a 1-bit counter. Someone asked me to use the 2 bulb version where everybody must have the same strategy. To me this means that no Jason can be selected in advance. I can solve it easily if the initial states are known or if there is a periodicity in the visits (the first visitor can set any initial state). The challenge I try to solve is: - Symmetric solution (i.e. identical algorithm for all prisoners, no leader appointed upfront) - Random timing - Unknown initial state

I suspect it's impossible - when you enter for the first time, the current configuration tells you nothing; the second time, assuming prisoners cycle through switch settings in a specific order, you can tell that at least k prisoners have entered since your last visit, where k is 0, 1, 2 or 3.

Actually, if the prisoners have access to a shared clock, then there is a strategy - I feel vaguely dirty for even suggesting it, but it could work:

Each prisoner starts with a (virtual) token and in a "dead" state. At agreed times start one of a reset phase, a count(n) phase or a share(n) phase (where the count(n) phase is the nth count phase). The switches are agreed to encode numbers 0, 1, 2 and 3.

During a reset phase, any prisoner who enters the room sets the switches to 0 and becomes "live".

During a count phase, any prisoner who enters the room to find both switches at 0 becomes "live", as do any prisoners who enter the room twice or more and see that the switches have changed between visits. Any prisoner who is "live" and has a token adds 1 to the switches if possible - if he does, he loses his token. Any prisoner who is "live" takes a note of the number represented by the switches, replacing any previous note for that count phase. At the end of the phase, all prisoners become "dead".

During a share(n) phase, any prisoner who enters to find the switches set to 0 or to less than their noted value for the corresponding count(n) phase becomes "live", as does any prisoner who enters multiple times during the phase and sees the switches changed. Any "live" prisoner compares their note for count(n) with the current value of the switches and updates their count(n) value to whichever of the two is greater, then sets the switches to that value. At the end of the phase, all prisoners become "dead".

As soon as any prisoner's noted counts sum to 100 (or 99 if they still hold a token) they can claim for release.

The order and lengths of the phases doesn't really matter, provided for each k, you have exactly one count(k) phase and an unlimited number of share(k) phases, and you have a reset phase between each pair of count(n) phases. Obviously there's no point having a share(k) phase before the count(k) phase, and reset phases should be fairly common - I'd say every odd-numbered phase.

Provided things are sufficiently random, eventually any given prisoner will be able to get rid of their token during some count(n) phase (with probability tending to 1), and every token that's been got rid of will be accounted for in someone's note for the corresponding count(n) phase (at the least, the prisoner whose token it was will have counted it) so eventually, with probability tending to 1, any other given prisoner will get that count in one of the corresponding share(n) phases...
 IP Logged
jollytall
Senior Riddler

Gender:
Posts: 585
 Re: 100 PRISONERS AND TWO LIGHT BULBS   « Reply #39 on: Jan 25th, 2015, 11:06am » Quote Modify

I like it, I think it is a valid solution. It is totally symmetrical during the whole cycle of the story. It is probably even more symmetrical than it was thought by the one who asked it (see below).
The tricky part is to choose the length and distribution of the phases smart. Probably, both the duration of the phases and their sequence shall be random, to avoid any interference with the frequency of the visits, should the guards follow a pattern.
To optimize it, probably the Share (n) phases (for a given n) shall get less frequent over time, on the basis that there is an increasing chance that the count of that phase is already shared to a wide enough audience.
Since it can take a very long time, the prisoners need an infinitely long "guide" of the sequence and duration of the phases. They can use e.g. the digits of PI or E or sqrt(2) to let them know what phase is next.
If I understand it correctly, this might even work with 1 switch.

My impression was that the increase of the number of the switches was to indicate if somebody "becomes" the Counter. I would assume that becoming a Counter during the process, based on the random sequence of visits does not violate the rule of following the same strategy. Nonetheless, I could not find any solution even with these rules. If there is any other hint from the guards (e.g. we take prisoners in at random times, but at least one per week, etc.) then it becomes very easy.
 IP Logged
 Pages: 1 2 Reply 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 »