wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> 100 PRISONERS AND TWO LIGHT BULBS
        
(Message started by: AlexH on Aug 23^rd, 2002, 9:21pm)

Title: 100 PRISONERS AND TWO LIGHT BULBS
Post by AlexH on Aug 23^rd, 2002, 9:21pm

Given N light bulbs and m prisoners, bulb 1 is going to be a control bulb and bulbs 2...N will be a N-1 bit counter. Designate a leader in the meeting. When the leader first enters the room, he toggles the control bulb and sets the counter to 0. Every subsequent time he enters the room he adds the counter to his tally and sets it to 0. When his tally hits m-1 he declares a win. All prisoners other than the leader increment the counter by 1 only if they haven't incremented it yet with control bulb in its current state, and only if the counter isn't already full. If k= 2^(N-1)-1 is the max value of the counter, then this method takes about cm^2/k + m ln k + m prisoner visits on average, where c is a value slightly over 1. One special case would be that if 2^N >= m, then we use an N-bit counter with wraparound and the first prisoner who sees the counter in a position indicating all m prisoners have incremented declares victory -- in such a case the win comes once the first person who entered the room reenters after all prisoners have visited the room.

I'm wasting a whole bulb due to the fact that we don't know the initial state of the bulbs, so I'm not at all sure this is optimal. One idea might be to have each prisoner send multiple counts so that we overcome the initial uncertainty due to the unknown state, but that seems like it would generally just be slower. The single light bulb problem turned out to be pretty interesting, so there may more to this than meets the eye.

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by Paul Hammond on Aug 24^th, 2002, 2:58pm

I don't see why you need a control bulb at all: the very first visitor just sets the N-bit counter to 1, subsequent new visitors increment it, and the leader resets it to zero when he visits. And therefore, when 2^N >= m, you could just say: first visitor sets the counter to 1, and as soon as the counter reaches m (or 0, in the case where 2^N = m), the current visitor declares victory. No need to wait for the first visitor to revisit. So they would declare victory as soon as they had all visited, and you can't do any better than that.

When 2^N is much less than m (as in the case of 100 prisoners, 2 bulbs), how about a multiple-counter method similar to that suggested for the original 1-bulb puzzle? Otherwise, it starts to resemble the inefficient "single leader" method:

Given N bulbs and P prisoners: 2^N different messages can be sent with N lights, so set up a heirarchy of Counters, with there being (2^N)-1 levels in the heirarchy, and each Counter within a level counting to the ((2^N)-1)th root of P.

To illustrate, with N=2 and P=100: (2^2)-1 = 3, cube root of 100 is between 4 and 5, so you'd have a 3-level heirarchy, and within each level, Counters would count to 4 or 5. Let's say Level1 Counters would count 5 prisoners each, so you'd need 20 of them. Of these Level1 Counters, some would also be Level2 Counters, who would count 5 Level1 Counters each, so you'd need 4 of them. Of these Level2 Counters, some would also be Level3 Counters, who would count 4 Level2 Counters each, so you'd only need one. He would be the person who eventually declares victory. The remaining 80 prisoners would be "drones". So the mechanism would be:

Drones would switch the lights to 0-1 the first time they entered the room and both lights were off.
Level1 Counters would reset any 0-1s they found to 0-0 and increment their tally. They would ignore the lights if they were in any other state. When their tally gets to five (including self) they would signal 1-0 and play no further part.
Level2 Counters would count 0-1s in the same way, but would also count 1-0 signals separately. They would ignore 0-0s and 1-1s. When both tallies reach 5 (including self) they would signal 1-1 and play no further part.
The sole Level3 Counter would count 0-1s, 1-0s and 1-1s separately. He would ignore 0-0s. When his three tallies reach 5/5/4 (including self), he would declare victory.
Special behaviour on the first visit: a drone would signal 0-1 regardless of the state of the lights, a Counter would reset the lights to 0-0.

(It's not actually necessary for Level(n) Counters to also be Level(n-1) Counters, it just makes it easier to describe the mechanism)

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by AlexH on Aug 24^th, 2002, 3:37pm

The problem with the first prisoner setting the counter to 1 is that he doesn't know he's the first prisoner.

On the other hand that idea for implementing the staged method from the 1 bulb problem by doing the stages simultaneously is very good. It doesn't help with just 2 bulbs unless we can get out of the control bulb problem, but for larger numbers its very interesting. You're right about a single counter looking a lot like the single leader model.

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by Paul Hammond on Aug 24^th, 2002, 4:24pm

Quote:

The problem with the first prisoner setting the counter to 1 is that he doesn't know he's the first prisoner

Ah. Once again, I overlook something :-[

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by AlexH on Aug 24^th, 2002, 10:56pm

I still don't have any bright ideas :P on the control bulb problem. Until a better idea than the control bulb comes along I'm just going to ignore it and focus on the other bulbs.

I've been thinking about the stages vs 1 counter thing and I think a mix of the 2 actually is best. Obviously once we get more than log (1+log n) data bulbs (i.e. enough to implement binary stages) then we will need to do something more with the extra space, such as be able to count multiple messages (or multiple instances of the same message) at one time. Even before that point though I think that we will gain from using some of our states to represent multiple messages rather than to enable new levels of messaging. This is all pretty much hand-waving intuition, but its my sense that the gains in using some bulb states to allow multiple messages (especailly those from level 0-- the drones-- for example) will win us a lot in terms of reduced congestion. Additionally since the log n sized digits was optimal in the 1 bulb problem, I'm inclined to think that reducing our digit size too far may actually be a losing proposition, or at least not enough of a win to outweigh the value of using that state to count another multiple.

Here is a concrete example of what I'm suggesting. Suppose we have 100 prisoners and 3 data bulbs. This would allow us to do binary stages with the 7 non-zero date bulb states. Instead I think it might be better to still have digits 5,5,4 and do something like:
0: no message
1: count 1 level 0
2: count 2 level 0
3: count 3 level 0
4: count 4 level 0
5: count 1 level 1
6: count 2 level 1
7: count 1 level 2

If we increase bulbs sufficiently we will start to have some states which combine messages from different levels.

Trying to analyze this theoretically is going to be really messy so I think I'll try to code a simulation.

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by Rupert on Aug 25^th, 2002, 2:19pm

[quote author=Paul Hammond link=board=riddles_hard;num=1030162865;start=0#3 date=08/24/02 at 16:24:09]

Ah. Once again, I overlook something :-[/quote]

Huh? Aren't we talking one prisoner per day? How could the first one not know he is first?

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by AlexH on Aug 25^th, 2002, 6:07pm

Rupert: The problem description says the warden lets prisoners into the room at arbitrary times rather than 1/day.

Haven't had much time to ponder this but 2 things come to mind. One is that it feels like there ought to be something sneaky to beat the control bulb method. Don't know how yet but there ought to be a way :P .

Second if we get to binary levels, then we could do the dynamic chosen levels thing again. The trick to make it work would be: when a prisoner with non-zero counter goes into the room and he sees a message on the bulbs that is higher level than the smallest message he has to send, he absorbs the message and sends his lowest level message instead. This is equivalent to just saying a prisoner always absorbs and then sends his lowest message -- which will often just be the message that was there in the first place. The tradeoffs between this method and pre-arranged levels method are not yet clear to me, but the dynamic method can be more cleanly bounded because it is faster than (though I think asymptotically equal to) the 1 bulb 1/day dynamic method which was O(n (log n)²). I still think the messier method combining levels and counters is probably faster, but once again I think the binary situation has a prettier looking solution.

Forgot to add one of the neat things about the dynamic binary method is that it doesn't require a <no message> state. There is always a message being sent, so we need N=1+ log log m bulbs. Edited to add: Not sure this is true actually. Some pesky details involving the guy who sets the control bulb which I had swept under the carpet. Will have to look at it more closely. At worst we go back to having a <no message> state and requiring the control bulb setter to be the one who declares victory.

In general we should probably just talk about how many states worth of information we have in the room. For example a discrete dial with k settings (like a thermostat).

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by Paul Hammond on Aug 26^th, 2002, 7:33am

I think you can solve the puzzle with only 1 light bulb, as follows:

The leader toggles the bulb every time he enters the room.
The other prisoners wait until they have seen the bulb in both states. Then, the first time they can turn the bulb on, they do.
If the leader finds the bulb switched on even though he switched it off on his last visit, he switches it off as usual and increments his tally.

Assuming this mechanism works, to use it with original N-bulb method above: the leader would keep toggling the control bulb, the others would increment the (N-1) bit counter only after they had seen at least one of the bulbs change state. If a prisoner found that the counter was full, but by chance the control bulb was off, he could switch it on and reset the counter, using the control bulb as an extra bit. So with 2 bulbs, you would have a sort of "1.5 bit" counter. The downside is that each prisoner would have to make at least 2 visits, possibly several more, before he could signal to the leader.

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by AlexH on Aug 26^th, 2002, 12:24pm

The "simple" solution to the 1 bulb problem where you don't know initial state is to have the leader model but each prisoner sends 2 messages. The initial state at worst throws off the tally by 1, so once the count gets to 198 he can declare victory. Your idea for the 1 bulb case is faster I think, though asymptotically the same.

The idea for partial control bulb is very similar to what I was working on. Use all bulbs for message states. No prisoner signals until he has seen a change. If the leader receives no message for the visit (possibly for small some number of visits in a row) he puts a bogus message on the wire and accounts for it. This integrates easily with having different levels or even dynamically chosing levels below the top, but we always need 1 pre-assigned top-level leader who will be the one who declares victory.

So for 100 prisoners and 2 bulbs, we'd use the 5,5,4 digit levels. All players are inactive until they see a change, the leader flicks to 0=<no message> when he enters room the first time , or if it was 0 originally he sends out some other message. These "fake" messages may be intercepted by some intermediary, but this will mean that some real message of that level will eventually be left over for the leader to absorb and account for the fake.

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by AlexH on Aug 29^th, 2002, 9:58pm

Finally had a bit of time and I coded a simulation for this problem type. With 2 bulbs and an unknown initial state, the method I described in my last post gives 2766 visits average to release. The current version uses a fairly simple method for deciding on fake messages: If the initial bulb state corresponded to 0 then on the first visit it sends a fake top level (i.e level 3) message, otherwise he just sets to 0. If the leader ever sees the same bulb state on a 3rd consecutive visit (i.e. he left it in that state, came back and saw that state and didn't change it, then came back again and it was still the same state and he can't change it without faking) then he aborbs the message if any or generates a level 1 fake if it the repeated state was 0.

If you do know the initial state of the bulbs then the 5,5,4 method gets you an average of 2268 visits so at present not knowing the bulbs initial state is costing nearly 500 visits(100 of which are just waiting for the leader to get there to start the process).

Next I want to try to see if the alternate counting idea can be an improvement even in the 2 bulbs case, but that means I'll have to generalize the algorithm even further so not sure when I'll get to it. In terms of counter values the 5,5,4 is basically 0,1,5,25. It suspect (though I'm not certain) that something like 0,1,10,11 or 0,1,2,10 might do better.

This algorithm (but with a 7 in a row threshold for doing fakes) gets 10583 visits with 1 bulb vs 10417 with 1 bulb and initial state known, so the cost of not knowing the state in the 1 bulb case is pretty small. 150 of the 166 difference is in the 100 visits (average) waiting for the leader to first visit, plus the extra 50% * 100 wasted when the initial state was 0 and the leader had send a fake 1 in order to make a change.

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by James Fingas on Aug 30^th, 2002, 8:58am

Alex,

I think that when we get to more than log(n) bulbs, we should implement a binary counter. Each person just increments the counter. To simplify (?) things, we could even count in gray code.

This still needs a solution to the initial state problem, but other than that, it's obviously optimal!

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by James Fingas on Aug 30^th, 2002, 9:13am

I've been thinking about the initial-state problem, and as I see it, you definitely need a pre-selected leader who has the authority to erase whatever the initial state of the lightbulb is. If you have more than one person who can do this, how can the first person guarantee that the second one won't go erasing something important?

Furthermore, the counting can't start until this leader erases the initial state, or the leader won't know whether or not counting has started.

Everyone else must be notified that the leader has erased the initial state, and this can't be done in a single visit, since anything they see in one visit could be the initial state. This can be done in two visits, if the leader makes sure that the "erased" state is different than the initial state.

Everyone has to observe a change before they'll signal to notify the leader. To expedite this, the leader should likely make sure to change the state of the bulbs every single time he enters the room, keeping track of any extraneous counters he must introduce.

Also, he should consider how he erases the initial state. If the initial state were "001", it might even be expedient for the leader to erase this by setting the lights to "010" instead of "000", as this would allow more people to be notified quickly (otherwise, the first person to notice that there has been a change would erase that change).

The control bit idea is based on a different principle: people start counting without knowing whether or not the leader has been there. They are later informed if the leader has not already been there. But this seems to me to require at least one bit of communication from the leader back to the other prisoners, likely increasing the incarceration time.

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by AlexH on Aug 30^th, 2002, 10:37am

James, just so its clear the control bulb idea was abandoned in the posts on the 26th. You are right about there being better "fake" message methods than the one I used in my test, I just chose something that seemed passable, easy to implement (streak counting), and not problem size dependent. I agree that setting to 0 when the initial state was 1 is probably not optimal in the 2 bulb 100 prisoner case. If I have a couple minutes I'll play with the initial state stuff for that specific problem. Haven't done anything more with generalizing to complex messages yet.

Added: Played with the fake message settings for a bit. Leader's first visit now implements: if the intial state wasn't <highest message>, set it to <highest message>, otherwise set it to 0. This gets us down to about 2580 visits in the 2 bulb 100 prisoner case. Intuitively we're making it likely that we get a large number of activations right away and the benefit outweighs the price of waiting for the leaders second visit before any "real" messages get sent.

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by shivbits1 on Sep 23^rd, 2002, 9:12am

;)
There seems to be something missing in the description of the puzzle...

Each day the jailor brings one prisoner to the living room.
the prisoners know they are 100 in number and they also know the Day he is going to start pulling prisoners into the living room...
So on the 100th day the prisoner who goes in knows that everyone has been to the room before?

seems too trivial so i'll assume the prisoners DO NOT know when the jailor is going to start pulling people into the living room and that the jailor DOES NOT necessarily call people into the living room Everyday.

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by James Fingas on Sep 23^rd, 2002, 10:16am

The important things you should know:

1) The prisoners don't know when they will start
2) The prisoners won't necessarily be called in one-per-day

Both of these are different from the "100 prisoners and one lightbulb" question. This thread is for the 2-lightbulb variation.

Most important however,

3) The selection of prisoners is random with replacement. This means that prisoner A may be called in twice (or more) before prisoner B is called in the first time.

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by marc van den bosch on Oct 31^st, 2002, 5:53am

You divide up the group in one counter and 99 countables.

Rules for Countables:
1. Countables cannot flick the switch unless on one of their previous visits
they have observed a different switch position.
2. Countables cannot flick the switch if they have already done so on one of
their previous visits
3. Countables cannot flick the switch if the switch position is XX
4. If Countables are allowed to flick the switch they must do so that:
00 becomes 0X
0X becomes X0
X0 becomes XX
Rules for Counter:
1. If the switches are set to anything but 00, the counter sets them to 00.
If the switches are set to 00 the counter sets them to XX
2. The counter counts as from the second time he enters the room and adds the number
(0X = 1, X0 = 2, XX = 3) to the total, unless he set the switches to position XX himself
the previous time.

I don't understand all the formula's and math, but this is the best set of rules I could get out of my tiny brain. :P

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by NeedQTIP2StabBrain on Nov 5^th, 2002, 1:17am

OK.. it's late here. one something in the morning. I havn't solved the problem, I just had a few additions. They may help someone else, but I need my sleep. On and Off are not the only possible positions. Either bulb could be on or off, screwed in or not, shattered or intact. This provides many more variables. I'll work on this when I'm at work. It's not like I have better things to do...

Nick

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by boschagal on Jul 14^th, 2005, 11:07am

i believe part of the problem is that every prisoner going to the room HAS to switch one switch and can't do more then that. is this correct?

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by River_Phoenix on Jul 14^th, 2005, 12:17pm

boschagal, there's many variations of the problem. In the case where the prisoners must flip one and exactly one switch, the easy solution to use the 2nd bulb as a dummy which gets switched back and forth by prisoners who do not want to flip the 1st bulb (which actually counts). For example:

Pick a leader. After his first visit, if the 1st bulb is on, he turns it off and increments his counter. Otherwise he toggles the 2nd bulb.

All other prisoners have this behavior: If the 1st bulb is off they flip it on if and only if they have not done so before, otherwise they toggle the 2nd bulb.

The leader will eventually count up to 100. That's among the SLOW solutions for this version of the problem.

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by Dan on Sep 5^th, 2005, 10:28pm

I'm very new at this but this is my proposed answer, since I can't really read your crazy math mumbo jumbo, I'll use my english. This is only a start, I still don't know how it would make a winning bid...

Since the prisoners don't know who is first, or if they are first and the initial state of the bulb. Then they need a control person. Every prisoner before the control, if he isn't chosen first, would keep 1 bulb open. This would ensure when the control came that he is the counter start. After this, He would turn both lights off. This would signal the next person, that he is Counter 1, then he would turn both of them on. The next person would go to the left bulb turning it off. Counter 2. The next person would turn off the right bulb and turn on the left bulb. Counter 3. and so on and so on. But i'm too dum to figure it out after that....

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by spiff on Sep 6^th, 2005, 12:51am

Here is my solution to the 100 prisoners and the light bulb.

All 100 of the prisoners are brought to the courtyard by a warden. 200 blank pieces of paper are put into a hat by the warden. The warden tells each prisoner to draw two papers from the hat. He also tells them to leave the bulb in the opposite of what it was when they entered the room.

They are also told to write which number they are on both pieces of paper when entering the room. If you are the first in the room, write the number 1 on both pieces of paper. Leave one of them on the table, the other in your pocket. All prisoners are told to do this, and choose the correct number to write on the papers based on the largest number left on the table when they enter the room. This is done to keep count of how many prisoners have entered the room. A pen will be left on the table for this. That is all that the prisoners are told.

The warden notes to himself; "All prisoners with an ODD number will tell me the light was OFF when they entered the room. All prisoners with an EVEN number will tell me that the light was ON when they entered the room.

Any prisoner who enters the room will know if all of the prisoners have entered the room or not because the numbers left on the table counts the number of prisoners who have been in the room. If there is less than 100 numbers on the table then not all of the prisoners have been to the room. So any prisoner but the 100th prisoner will know not to assert that all of the prisoners have entered the room.

Only the 100th prisoner to enter the room will know that he is the 100th prisoner to enter the room. He also knows that he is the only one who can make the assertion that all 100 prisoners have entered the room.

The warden can prove that all 100 prisoners have been to the room by going to each cell and asking each prisoner what their number is and if the light was on or off when entering the room. The prisoner can pull his number from his pocket to prove which number he is and every prisoner will be able to tell the truth to the warden when asked if the bulb was on or off when entering the room. No two prisoners will bare the same number.

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by Grimbal on Sep 6^th, 2005, 1:33am

Hmmm... You mean the prisonners could pretend to be someone else to get an early liberation and the wardens must prevent it? Then the warden could just give receipts to all prisonners who were called in. But my understanding was that the wardens know perfectly well which prisonner they call in.

And I don't see the point of drawing papers from a hat if the papers are still white at that point.

???

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by thrillseeker on Sep 6^th, 2005, 3:20am

I failed to notice that I was responding to the wrong riddle. But, the solution I provided can still be used for the 2 bulb riddle.

All of the prisoners are brought to the cafeteria and supervised by a warden who notes everything that is said.

One prisoner has determined how the correct assertion will be made. He is trusted by all the prisoners.

Each prisoner is given 2 blank pieces of paper.

Names are given to both bulbs. The names are bulb 1 and bulb 2. The prisoners and the warden understand which bulb is bulb 1 and which bulb is bulb 2.

They are also told, "If you are the first prisoner to enter the room, you will know this because there are no pieces of paper on the table. If you are the first prisoner to enter the room, write the number 1 on both pieces of paper. Leave one numbered piece of paper on the table before you exit the room and put the other in your pocket and never lose it. All prisoners who enter the room, note the highest number on the table. Your number is the number following that number. Write that number on both pieces of paper. Leave one on the table before you exit the room and put the other in your pocket and never lose it."

They are also told that only the 100th prisoner to enter the room can make the assertion that all 100 prisoners have entered the room.

They are told that if any prisoner is sent to the room twice, not to leave another numbered piece of paper on the table and not to put any numbered piece of paper in their pocket again. And not to tamper with the bulbs in any way.

They are told to exit the room with the bulbs in the opposite state of what they were when they entered the room. If bulb 1 was ON, turn it OFF. If bulb 1 was OFF, turn it ON. The same applies for bulb 2.

The prisoner who has planned all of this tells the warden in private without the others hearing, "All prisoners who have an ODD number will tell you the SAME STATE for the bulbs when they entered the room. All prisoners with an EVEN number will tell you the OPPOSITE STATE of the bulbs when they entered the room than the prisoners with the ODD numbers." All prisoners return to their cell.

Only the 100th prisoner will know that he is the 100th prisoner to enter the room because there will be 99 numbered pieces of paper on the table when he enters the room. He also knows that he is the only prisoner who can make the assertion that all of the prisoners have entered the room.

The warden can prove that all 100 prisoners have been to the room by going to each and every one of the prisoners cells and asking them, "What is your number and what was the state of bulb 1 and bulb 2 when you entered the room?"

All EVEN numbered prisoners will have the same answer. All ODD numbered prisoners will have the same answer and the opposite answer of the EVEN numbered prisoners.

Each prisoner can prove what number he is by pulling the duplicate number out of his pocket.

No two prisoners will bare the same number.

If the warden is not allowed to be present while the prisoners are in the cafeteria desiging a plan then I believe this alternate solution will work....

The prisoners must be told that if you are the 100th prisoner to enter the room, you must make the assertion that all prisoners have been to the room AND you must tell the warden to go to each cell and ask each prisoner, "What is your number and what was the state of bulb 1 and bulb 2 when you entered the room?" The 100th prisoner to enter the room must also tell the warden this, "The prisoners kept track of what number prisoner they were to enter the room and they can prove what number they were by presenting you with a number that is in their pocket. No two prisoners will have the same number. Prisoners with an ODD number will tell you the SAME STATE for both bulbs when they entered the room. Prisoners with an EVEN number will tell you the OPPOSITE STATE than the ODD numbered prisoners." He must also be explained which bulb is bulb 1 and which bulb is bulb 2.

The fact that this information was presented to the prisoners prior to the start of the whole thing is irrelevent because the initial state of the bulbs is unknown by everyone.

How could all the ODD numbered prisoners know the SAME STATE for the bulbs if they had not entered the room? They know that all the ODD numbered prisoners will say the SAME STATE before starting, but they will not know what that state is, and neither will the EVEN numbered prisoners.

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by thrillseeker on Sep 6^th, 2005, 3:56pm

There is only problem that I can see with the way that the riddle is stated. The prisoners are not asked to prove to the warden if all 100 of the prisoners have been to the room. Because of this, there is no need for 2 or even 1 lightbulb to be a part of the riddle. A simple hand held counter could be used. The counter is intially set at zero. When you enter the room for the first time, click the counter adding one more number to it. If you are sent to the room more than once, do not add another number to the counter. When a prisoner comes into the room and sees the number 99 on the counter, he knows that he is the 100th prisoner and can now make the assertion that all 100 prisoners have been to the room. Merely showing the warden the number 100 on the counter proves nothing because whos to say that the prisoner who makes the assertion didnt just click the counter 100 times himself?

This is the reason for my solution as described in my earlier response. The lightbulbs MUST be used as a part of the solution or it is a bogus riddle.

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by Icarus on Sep 6^th, 2005, 6:23pm

thrillseeker, I think you are misinterpreting both versions of this riddle. The warden is not some nice guy who is trying his best to help these prisoners meet a condition for leaving. The warden is the evil capricious soul who sets a fiendish time-consuming task to the prisoners as their only hope of every attaining release from solitary confinement. He isn't going to give them extra equipment - not even slips of paper - that will make their task easier.

If the prisoners could leave anything in the room, the problem becomes trivial. The problem is non-trivial (i.e. - interesting), when the only means the prisoners have of communicating after the initial meeting is by whether the light switches are on or off. No other changes to the room and its contents are allowed by the guards.

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by thrillseeker on Sep 6^th, 2005, 8:56pm

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.

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by Grimbal on Sep 7^th, 2005, 2:22am

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.

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by rmsgrey on Sep 7^th, 2005, 4:57am

on 09/07/05 at 02:22:27, Grimbal wrote:

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?

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by thrillseeker on Sep 7^th, 2005, 9:07pm

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.

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by thrillseeker on Sep 7^th, 2005, 9:32pm

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

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by rmsgrey on Sep 8^th, 2005, 4:33am

on 09/07/05 at 21:07:43, thrillseeker wrote:

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.

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by thrillseeker on Sep 8^th, 2005, 8:55pm

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? ???

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by Grimbal on Sep 9^th, 2005, 12:38am

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.

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by thrillseeker on Sep 9^th, 2005, 9:48am

on 09/09/05 at 00:38:42, Grimbal 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.

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by Grimbal on Sep 10^th, 2005, 4:06am

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.

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by rmsgrey on Sep 10^th, 2005, 7:05am

on 09/09/05 at 09:48:57, thrillseeker wrote:

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.

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by thrillseeker on Sep 12^th, 2005, 7:26pm

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 choose a leader....Jason

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. 8) :-/

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by jollytall on Jan 24^th, 2015, 12:01pm

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

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by rmsgrey on Jan 25^th, 2015, 10:07am

on 01/24/15 at 12:01:43, jollytall wrote:

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...

Title: Re: 100 PRISONERS AND TWO LIGHT BULBS
Post by jollytall on Jan 25^th, 2015, 11:06am

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.