Author |
Topic: 100 PRISONERS AND TWO LIGHT BULBS (Read 18178 times) |
|
AlexH
Full Member
Posts: 156
|
 |
100 PRISONERS AND TWO LIGHT BULBS
« on: Aug 23rd, 2002, 9:21pm » |
 Quote  Modify
|
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.
|
| « Last Edit: Aug 23rd, 2002, 10:21pm by AlexH » |
 IP Logged |
|
|
|
Paul Hammond
Newbie
Posts: 29
|
|
Re: 100 PRISONERS AND TWO LIGHT BULBS
« Reply #1 on: Aug 24th, 2002, 2:58pm » |
Quote Modify
|
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)
|
|
IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: 100 PRISONERS AND TWO LIGHT BULBS
« Reply #2 on: Aug 24th, 2002, 3:37pm » |
Quote Modify
|
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.
|
| « Last Edit: Aug 24th, 2002, 4:02pm by AlexH » |
IP Logged |
|
|
|
Paul Hammond
Newbie
Posts: 29
|
|
Re: 100 PRISONERS AND TWO LIGHT BULBS
« Reply #3 on: Aug 24th, 2002, 4:24pm » |
Quote Modify
|
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 
|
|
IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: 100 PRISONERS AND TWO LIGHT BULBS
« Reply #4 on: Aug 24th, 2002, 10:56pm » |
Quote Modify
|
I still don't have any bright ideas  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.
|
|
IP Logged |
|
|
|
Rupert
Newbie
Gender: 
Posts: 11
|
|
Re: 100 PRISONERS AND TWO LIGHT BULBS
« Reply #5 on: Aug 25th, 2002, 2:19pm » |
Quote Modify
|
on Aug 24th, 2002, 4:24pm, Paul Hammond wrote:
Ah. Once again, I overlook something |
|
Huh? Aren't we talking one prisoner per day? How could the first one not know he is first?
|
|
IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: 100 PRISONERS AND TWO LIGHT BULBS
« Reply #6 on: Aug 25th, 2002, 6:07pm » |
Quote Modify
|
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 .
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)2). 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).
|
| « Last Edit: Aug 26th, 2002, 1:23am by AlexH » |
IP Logged |
|
|
|
Paul Hammond
Newbie
Posts: 29
|
|
Re: 100 PRISONERS AND TWO LIGHT BULBS
« Reply #7 on: Aug 26th, 2002, 7:33am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: 100 PRISONERS AND TWO LIGHT BULBS
« Reply #8 on: Aug 26th, 2002, 12:24pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: 100 PRISONERS AND TWO LIGHT BULBS
« Reply #9 on: Aug 29th, 2002, 9:58pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: 100 PRISONERS AND TWO LIGHT BULBS
« Reply #10 on: Aug 30th, 2002, 8:58am » |
Quote Modify
|
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!
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: 100 PRISONERS AND TWO LIGHT BULBS
« Reply #11 on: Aug 30th, 2002, 9:13am » |
Quote Modify
|
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.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: 100 PRISONERS AND TWO LIGHT BULBS
« Reply #12 on: Aug 30th, 2002, 10:37am » |
Quote Modify
|
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.
|
| « Last Edit: Aug 30th, 2002, 11:12am by AlexH » |
IP Logged |
|
|
|
shivbits1
Newbie
Posts: 3
|
|
Re: 100 PRISONERS AND TWO LIGHT BULBS
« Reply #13 on: Sep 23rd, 2002, 9:12am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: 100 PRISONERS AND TWO LIGHT BULBS
« Reply #14 on: Sep 23rd, 2002, 10:16am » |
Quote Modify
|
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.
|
| « Last Edit: Sep 23rd, 2002, 10:17am by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
marc van den bosch
Guest
|
|
Re: 100 PRISONERS AND TWO LIGHT BULBS
« Reply #15 on: Oct 31st, 2002, 5:53am » |
Quote Modify
 Remove
|
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.
|
|
IP Logged |
|
|
|
NeedQTIP2StabBrain
Newbie
  
Gender:
Posts: 4
|
|
Re: 100 PRISONERS AND TWO LIGHT BULBS
« Reply #16 on: Nov 5th, 2002, 1:17am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
boschagal
Guest
|
|
Re: 100 PRISONERS AND TWO LIGHT BULBS
« Reply #17 on: Jul 14th, 2005, 11:07am » |
Quote Modify
Remove
|
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?
|
|
IP Logged |
|
|
|
River Phoenix
Junior Member
Gender:
Posts: 125
|
|
Re: 100 PRISONERS AND TWO LIGHT BULBS
« Reply #18 on: Jul 14th, 2005, 12:17pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Dan
Guest
|
|
Re: 100 PRISONERS AND TWO LIGHT BULBS
« Reply #19 on: Sep 5th, 2005, 10:28pm » |
Quote Modify
Remove
|
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....
|
|
IP Logged |
|
|
|
spiff
Guest
|
|
Re: 100 PRISONERS AND TWO LIGHT BULBS
« Reply #20 on: Sep 6th, 2005, 12:51am » |
Quote Modify
Remove
|
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.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: 100 PRISONERS AND TWO LIGHT BULBS
« Reply #21 on: Sep 6th, 2005, 1:33am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
thrillseeker
Newbie
Posts: 22
|
|
Re: 100 PRISONERS AND TWO LIGHT BULBS
« Reply #22 on: Sep 6th, 2005, 3:20am » |
Quote Modify
|
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.
|
| « Last Edit: Sep 6th, 2005, 3:35am by thrillseeker » |
IP Logged |
|
|
|
thrillseeker
Newbie
Posts: 22
|
|
Re: 100 PRISONERS AND TWO LIGHT BULBS
« Reply #23 on: Sep 6th, 2005, 3:56pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: 100 PRISONERS AND TWO LIGHT BULBS
« Reply #24 on: Sep 6th, 2005, 6:23pm » |
Quote Modify
|
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.
|
|
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
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print