# 5 Star Logic Problem (100 prisoners and a light bulb)

Hey man. They are prisoners after all.

The answer to the original post is obvious. These are after all prisoners and can't really be expected to tell the truth. It does not state that the warden keeps track of which prisoners are chosen. Therefore, The plan they decided on was after 101 days, they all agree that they have been in the room.

I think I found a way to optimize the time it takes to be sure all 100 prisoners have been in the room. (For simplicity though I’m going to use 128 prisoners but this is easily simplified, just not easily explained) This gets a little complicated so Ill do my best. This idea is based off another posters idea. This idea uses a binary technique. There will be 8 “levels” in this method and we will use the idea of handing off counters (just imaginary objects to keep track of how far along hey are.) Only designated people can “keep” a counter. Once a designated person has 2 counters they can hand off their counter. Anyone can “take” a counter that is not supposed to “keep” the counter (this gives them an extra counter to keep track of.) First off there are 8 designated days 1 for each level. One person is the level 1 keeper. The level 1 keeper and 1 another designated person are level 2 keepers. Those 2 plus 2 others are level 3 keepers… Those 32 plus 32 more are level 7 keepers. Everyone is given a level 8 counter.

On the first day of the cycle if the random person has not given away their level 8 counter they turn on the light. If they have they leave the light off.

On the second day of the cycle:
If the light is on and the prisoner is a level (L) 7 keeper, he keeps the L7 counter and turns off the light.
If the L7 keeper now has 2 L8 counters he leaves the light on.
If the light is on and the prisoner is not a L7 keeper they “take” the L8 counter for later and turns off the light.
If the light is off the prisoners do nothing.

On the third day of the cycle:
If the light is on and the prisoner is a L6 keeper, he keeps the L6 counter and turns off the light.
If the L6 keeper now has 2 L7 counters he leaves the light on.
If the light is on and the prisoner is not a L6 keeper they “take” the L7 counter for later and turns off the light.
If the light is off the prisoners do nothing.

On the (9-x) th day of the cycle: (this is tricky because on day 4 x=5 ect.)
If the light is on and the prisoner is a Lx keeper, he keeps the Lx counter and turns off the light.
If the Lx keeper now has 2 L(x+1) counter he leaves the light on.
If the light is on and the prisoner is not a Lx keeper they “take” the L(x+1) counter for later and turns off the light.
If the light is off the prisoners do nothing.

After 8 days the cycle starts all over again with day 1.

When the designated level 1 keeper has both his level 2 counters he can declare all 128 have been in the room.

(Let me know if I need to explain better)

Making this for only 100 people you simply give 28 prisoners an extra L8 counter. If given to the correct people this can greatly reduce the amount of handoffs that need to take place.

Uhh, the plan will be before anything the first person picked will assert that they know not everyone has gone. Thus, their assertion is correct.

"If the light is on and the prisoner is not a L7 keeper they “take” the L8 counter for later and turns off the light."
Who are they?

What if a designated L3 keeper (keeps one L4 counter) was randomly choosen to enter the room 8 times, and the ninth time he follows an L8 level prisoner choosen for the first time to enter the room?

Q: How can the prisoners tell, with certainty, that all 100 of them have visited the central living room with the light bulb.

The riddle: 100 prisoners are in solitary cells, unable to see, speak or communicate in any way from those solitary cells with each other. There's a central living room with one light bulb; the bulb is initially off. No prisoner can see the light bulb from his own cell. Everyday, the warden picks a prisoner at random, and that prisoner goes to the central living room. While there, the prisoner can toggle the bulb if he or she wishes. Also, the prisoner has the option of asserting the claim that all 100 prisoners have been to the living room. If this assertion is false (that is, some prisoners still haven't been to the living room), all 100 prisoners will be shot for their stupidity. However, if it is indeed true, all prisoners are set free. Thus, the assertion should only be made if the prisoner is 100% certain of its validity.

Before the random picking begins, the prisoners are allowed to get together to discuss a plan. So ---- what plan should they agree on, so that eventually, someone will make a correct assertion?

At this meeting, 100 cards are made, numbered from 1 to 100, and passed out to each prisoner. When they go to the central room, they leave the card. When all 100 cards are there, that last person to place in that missing, last card, calls the warden.

okay i registered just there. I think the answer is pretty obvious. :p its got nothing to do with a lightbulb

Each time somebody goes in there, they take off there top and leave it in the living room. And if they return for a second third or fourth time they still leave it there. If any prisoner ever returns more than once they dont do anything, just leave there top there. Everytime someone returns they count the number of tops in the living room. Once someone who hasnt been in there counts 99 tops + takes off there own top then that means all 100 have visited. creative thinking eh? :p

BobG
Homework Helper
At this meeting, 100 cards are made, numbered from 1 to 100, and passed out to each prisoner. When they go to the central room, they leave the card. When all 100 cards are there, that last person to place in that missing, last card, calls the warden.

okay i registered just there. I think the answer is pretty obvious. :p its got nothing to do with a lightbulb

Each time somebody goes in there, they take off there top and leave it in the living room. And if they return for a second third or fourth time they still leave it there. If any prisoner ever returns more than once they dont do anything, just leave there top there. Everytime someone returns they count the number of tops in the living room. Once someone who hasnt been in there counts 99 tops + takes off there own top then that means all 100 have visited. creative thinking eh? :p

The only means of communication is the light bulb, so both solutions are wrong.

Interesting discussion. In deciding whether the 99.999% probability or the 100% single counter method is 'best', consider that it only took 19 years for Andy Dufrene to tunnel out of Shawshank with a 6" rock hammer. :rofl: (I just happened to watch that movie on TV today)

This is an old problem, but I'd never considered how long it would take for the 'correct' solution to pan out. Time puts a whole new spin on the problem.

Strilanc
I saw an interesting solution to this problem. You consider turning on the light bulb as depositing souls and when one prisoner has all the souls he announces. Then a series of periods is defined, where the value of the light bulb is 2^n souls.

Initially, all prisoners have one soul. If they enter the room and there is no soul (the light bulb is off) they deposit their soul. Otherwise they take the soul and hold on to both until the next period starts. During the second period the light bulb is worth two souls and prisoners with two souls deposit them/take them. This continues until it is likely that one prisoner has all the souls.

If no one announces, the cycle of periods starts over. I don't remember the length of each period, but the estimated escape time was much better than the single counter scenario.

It's quite simple really. Since all the prisoners can meet together and discuss whatever they want before the pickings, I decided to make them discuss their plan. Well what happens is that they tell eachother that when thy go into the room they will mark their initials onto the wall in the room. To make sure that the guards do not see them doing this they will turn off the light and then mark the wall with whatever they have at hand whether it be fingernails or whatever. In the even that a person has the same initials as another person then he/she will just mark a line under those intials. If a person gets picked multiple times the prisoner will not do anything to the wall. Every time someone goes into the room they will check the wall to see how many intials are on the wall. When someone goes in and see all 100 initials on the wall they will then say that all 100 prisoners have been in this room. This process can take any amount of days between 100 and beyond with there being no limit tohow many times a prisoner can be picked. resulting in some prisoners not being picked for a possibly long time. But in the end once all 100 HAVE been picked then the next person to go in WILL know that all 100 have been picked.

Last edited:
when thy go into the room they will mark their initials onto the wall in the room.

Nope, disallowed. They have two options when they are in the room:
1) Toggle light
2) Make the assertion

That's it. No writing initials, no tapping in morse code, no removing clothing, no nothing, apart from toggling the light and making the assertion. I suppose it's possible that they aren't even allowed to breathe while in the room (they just can't stay in very long). From the original problem:

"While there, the prisoner can toggle the bulb if he or she wishes. Also, the prisoner has the option of asserting the claim that all 100 prisoners have been to the living room."

Otherwise, yeah, it's simple.

DaveE

This is why I said they will turn off the light and then do it to remove any suspicion. If the guards cannot see what is going on then how will they stop them? Unless this is disallowed by the rules of the riddle and not necisarrily the guards rules then it is wrong.

Last edited:
Unless this is disallowed by the rules of the riddle and not necisarrily the guards rules then it is wrong.

Exactly. Rules of the riddle. The important parts of the riddle were that you have a light bulb (really a light switch) that you can flip, and you have to use that (and only that) to make the assertion on whether or not all the prisoners have visited the room.

For all intents and purposes, for the sake of the riddle, you can pretend that these stipulations were made:

1) The guards do not approve of the warden's decision, and will try at every opportunity to keep the prisoners from successfully making the assertion that all prisoners have been to the room.

2) In between inmate visits, guards can alter the room in any way they see fit EXCEPT that the switch MUST be in exactly the same position for a newly arrived prisoner as it was when the previous prisoner left.

3) The guards are allowed to listen while the prisoners develop their plan.

Dave

Last edited:
Well in all i thought it was a pretty good answer but if it wasnt against the riddle rules then it could have possibly been right. But oh well ill try coming up with another answer later.

you almost gave me a shudder, completly forgot about this question but my answer has changed. i'd say each prisoner trys to mind meld with the light bulb while it wheels (see taylor-wheeler theory).

PLAN

#1 If light is ON, leader turns light OFF.
#2 If a prisoner sees light OFF for the first time, he turn light ON
#3 After the leader turned light OFF 99 times, he claims (100% sure) that all 100 prisoners have been to the room.

Note: If light is already OFF, leader does nothing. If light is already ON, prisoner does nothing. If prisoner sees light OFF for the second time, he does nothing.

Last edited:
PLAN

#1 If light is ON, leader turns light OFF.
#2 If a prisoner sees light OFF for the first time, he turn light ON
#3 After the leader turned light OFF 99 times, he claims (100% sure) that all 100 prisoners have been to the room.

Note: If light is already OFF, leader does nothing. If light is already ON, prisoner does nothing. If prisoner sees light OFF for the second time, he does nothing.

Well, this has been already written in post #2...

Well, this has been already written in post #2...
Wow! I did not see...

Q:Before the random picking begins, the prisoners are allowed to get together to discuss a plan. So ---- what plan should they agree on, so that eventually, someone will make a correct assertion?

During the planning phase, all of the prisoners get together IN THE CENTRAL LIVING ROOM.

Therefore, they would have all been in the room on day 1 and would be able to get out as soon as possible.

so far the only way i can see of "solving" it is using probability
however i dont believe this is a valid solution as the question stipulates that the declaration must be 100%
and one thing i know about probability is that if i flip a coin 10^10000000000 times i cannot say 100% that it wont heads every time.

therfore the prisioners could spend infinity^infinity eons locked up and still not be sure 100%

so there must be a soln that does not rely on prob or silly invention
i think this one may drive me crazy

I think I've figured out the answer. Since they all get to meet together before they go in their cells what they will do is they wil devise a plan where the person who's cell is closest to the room's entrance will be the person who'll know how many people have gone. what happens is even though at the time they may not know who is going to be closest until they receive their cells is that the person going by the cell and into the room with the bulb wil shout out his/her name while walking by. If the person has already gone then they will say nothing. The person in the cell closest will keep track of all the names called in one way or another and when all 100 have called out their names and finally the person closest goes after al names have been said he/she will tell the guards they all have went. Depending on how many days it takes for everyone to go then there is no possible way to tell exactly how many days before their final day in the facility.

Last edited:
assuming all prisoners can count the days:

each toggles the switch everyday
if your called on an odd day the switch should initally be on
if your called on an even day the switch should initally be off
if your called twice within 100 days you leave the light bulb as it is
alerting the next guy that someone was called twice by destroying the correspondence between odd-on even-off [we call this guy THE MASTER]

the next guy continues to alert everyone that its a bum deal by continuing to toggle the switch
all prisionsers will know that its bad because on/off dont match with the even odd days.

UNTILL the original guy who was called twice returns having counted at least 100 days since his last visit. he now restores order (off for odd days on for even days).

the system is reset
each prisioner again toggles the switch on for odd days off for even days
again, if one man is called twice within 100 days he leaves the switch destroying the order.[HE BECOMES THE MASTER]

finally when our man [the master] who restored the order returns, again having counted 100 days at least and seeing that odd/even days match with on/off he knows that no one prisioner has been called twice in the last 100 days. and seeing as there is only 100 prisioners this means that each prisioner must have been called at least once.

he declares this and is promplty taken out to the back of the pump house and shot!

now where do i collect my prize (probably at the back of the pump house?! :) )

also i note from my post above that by the time dude decalers that all prisioner have been at least once, it may be several years since the event actually occuring. but he does not know this, not 100%

also i just read akg's post #2 properly and i think if he and i were prisoners i'd rather go with his method!
28 years is easssyyy time

My Solution:

1. First prisoner who goes to central room acts as counter and he leaves the switch as it is i.e off
2. Different prisoner goes to central room turns the light on if it is switched off and he/she
should not turn it on/off from then, even he/she gets chance to enter central room again(goes to infinity)..
3. Different prisoner goes to central room leaves the light as it is, if it is switched on
4. So whenever the first prisoner gets chance to go to central room again,he will count 1 if
the light is switched on and make the switch off.
5. when the first prisoner who is counting gets 99,then he will tell that all 100 prisoners
have been to the central room

This method takes a long long time but will work. please tell me if there are any mistakes

Well, I didn't know how to do that math, but I do know how to program a computer. So I wrote a simulation of AKG's method. After running the program several times (each time the program averages 1000 runs) I got a pretty consistent result.

The most likely number of days that the prisoners would serve would about 10,420 days. That a little over 28 years. That's the most likely amount of time they would serve using AKG's method.

If you'd like to see my program I'll be glad to post it. I wrote it in Visual Basic and it's quite short.

There's probably some way to do this directly using probability mathematics.

I've done a script in PHP. Running 10000 Trials the results come out to:

Max: 14348
Min: 6780
Avg: 10010.3376

So this number is very close to 10000 which is correct even intuitively seeing that the counter person has to come back to the room 100 times at a rate of 1/100 of him being chosen. Equals to 100x100 = 10,000 days.