100 prisoners are imprisoned in solitary cells. Each cell is windowless and soundproof. There's a central living room with one light bulb; the bulb is initially off. No prisoner can see the light bulb from his or her own cell. Each day, the warden picks a prisoner equally at random, and that prisoner visits the central living room; at the end of the day the prisoner is returned to his cell. While in the living room, 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 and inducted into MENSA, since the world can always use more smart people. Thus, the assertion should only be made if the prisoner is 100% certain of its validity.
Before this whole procedure begins, the prisoners are allowed to get together in the courtyard to discuss a plan. What is the optimal plan they can agree on, so that eventually, someone will make a correct assertion?
>>7687251
More @ https://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml
What if randomly, one person is never picked?
>>7687274
after infinite time he will have been picked
>>7687251
Choose one person to keep track. Every time he enters the room, if the light is on, he turns it off and adds 1 to a tally. When any other person enters the room, if the light is off and they have never turned it on before, they turn it on; otherwise they do nothing. Once the guy counting reaches 99, everyone has been in the room.
>>7687288
There are better methods with better averages m8
>>7687293
So share with the class, faggot.
>>7687251
>equally at random
>a person can be chosen more than once
It's unsolvable except by use of statistics at which point it still has an error rate
Or am I reading this incorrectly?
OHWAIT I GOT IT
They plan is the first guy to go in leaves the bulb on and then let the rest persons go through and leave it on, when the bulb burns out that is the optimal time to assert that all the persons have been through the room...
...
>other than that ...
every person should smash the lightbulb and then be told that they need a new one
>repeat the process till swimming in glass
>???
>Enjoy the bullet of mercy
The prisoners agree to cheat.
>>7687327
>being this retarded
>>7687338
Yeah I legit fuq'd up
> >>7687288 is the winrar of garenteed success
Are they allowed to count the days since the it started? That way the first prisoner would know he is the first.
The prisoners decide to leave the light on if it was their first time visiting the living room and off if they had already been there. Whenever a prisoner is taken to the living room they take note if the light was turned on, so each prisoner will separately count how many times they've found the light turned on.
Once any prisoner has counted finding the light on 100 times they can say that all prisoners have visited the living room.
>>7687322
The following algorithm takes all of these factors into consideration, and is also mathematically appealing:
Every prisoner starts off with a count of 1.
Designate one prisoner as the "collector".
Divide time into 7 phases, each 460 days long, which cycle from 0-6 forever.
If the light is on when a prisoner enters, and their count has the bit corresponding to 2phase set, they increase their count by 2phase and turn off the light.
The only exception is on the last day of each phase, prisoners must turn off the light if it is on, increasing their count by 2phase.
If the prisoner is not the collector, and their count has the bit corresponding to 2phase set, they turn on the light.
When the collector has reached a count of 100, they notify the warden.
Average 13.3 years
Now go kill yourself you retarded faggot.
No one will miss you
>>7687322
another
Every prisoner starts off with a count of 1.
Designate one prisoner as the "collector".
The collector has a "master count" that starts at 0.
Designate a "assistants".
Divide time into 2 phases, each 2400 days long, which cycle from 0-1 forever.
If the light is on and it is the first phase when an assistant enters, they increase their count by 1 and turn off the light.
If the light is on and it is the second phase when the collector enters, they increase their master count by 100/a and turn off the light.
There are exceptions on the last day of each phase: At the end of the first phase, prisoners must turn off the light if it is on, increasing their count by 1. At the end of the second phase, prisoners must turn off the light if it is on, increasing their count by 100/a, and they get promoted to assistant.
In the first phase, if a prisoner has a count greater than their quota (i.e. greater than 0 for normal prisoners, greater than 100/a for assistants), then they decrease their count and turn on the light.
In the second phase, if an assistant has reached their quota (count is greater than 100/a), they decrease their count by 100/a and turn on the light.
When the collector has reached a master count of 100, they notify the warden.
10.67 years on average
Please stream your suicide so that we can laugh at the plebs of sci :)
>>7687288
nice. yeah that'd work. would take a bit of time tho
>>7687435
haha rekt
>>7687367
Average of 27 years, would rather get shot
>>7687435
Fokin destroyed
>>7687288
But what about if someone was in the room two times earlier? They would turn off the light next time and make it inaccurate by one, hence never reaching 99
if allowed to make a sign or mark on the centre living room. make a visible tally/log for people to sign. when a person who hasn't been to the room is in the room, he signs the tally. He then needs to remember if he's signed the log. If a person who has already been to the room and is in the room again. He leaves the log alone.
When a person who hasn't been to the room and sees 99 tally's on the log he may claim that all 100 including himself has been.
If not allowed to make a mark on the centre living room i dunno wait a really long time before one person will claim. I'm thinking atleast a year
>>7687251
Choose one prisoner as the decider.
The decider, upon entering the room, will turn the bulb off if it is on, and add 1 to a mental tally he is keeping. If the bulb is off he leaves it off and does not increment his tally.
Every other prisoner will turn the bulb on the first time he enters and the bulb is off, otherwise they will not toggle the switch.
Once the decider's tally reaches 99, he knows that every prisoner has been in the room.
>>7687251
>go to room
>if never been in the room, make a tally on the wall with own blood
>if someone new to room counts 99 tallies, all free
alternatively
>go to room
>commit suicide
>after 3 or 4 deaths, prison shuts down due to death counts
>prisoners transferred to another prison (ergo escaped from original)
>>7689394
>escaped from original
meant, 'free' from original prison
>>7687251
>equally at random
i dont know how youre defining "equally random" sounds to me like at 100 days they shouldve each been equally chosen once and so whoever was selected for day 100 should say they've all been in and the light was a red herring.
>>7687251
Pretty boy.
I would just say to wait four years and when someone is ballsy enough just call it out. I wouldn't want to spend any more than that locked up so kill me anyways, whatever
I didn't see anything about the prisoners not being allowed to do something like,"Everyone who has been to the room raise your hand." Unless someone wants to die, this plan would work because if 100 people want to live, they'll answer honestly, and theres nothing in the question saying I can not do this. You guys are overthinking this, and besides, it explicitly states in the riddle that no one can keep track of the light bulb because no one can see it.
You people are stupid. The lightbulb was a red herring.
>prisoners write their names on the wall when they go to the room
>when somebody sees that there are 100 names, they assert that everyone has been in the room
/end
>>7689628
Soundproof/windowless solitary cells, nimrod.
>>7687251
>What is the optimal plan they can agree on
"Okay this is ridiculous, lets all just get shot and move on with our lives?"
Each prisoner only toggles once. If they are selected twice they don't toggle. After 100 toggles are observed then its good.
>>7687367
>he light on if it was their first time visiting the living room and off if they had already been there. Whenever a prisoner is taken to the living room they take note if the light was turned on, so each prisoner will separately count how many times they've found the light turned on.
>Once any prisoner has counted finding the light on 100
this is retarded and doesn't work. It is possible that everyone goes into the room in 100 days. Then everyday after this will result in the light being turned off. No one will see the light on 100 times
>>7687251
The cells are made of glass, prisoners give thumbs up if theyve been in the room. I cant think of another way which wouldnt end up with them being dead due to time taken.
>>7689702
Or 99 names if they havent been in the room yet.
>>7687278
>after infinite time he will have been picked
First off, no, that's not right.
As time approaches infinity, the odds of him remaining unpicked approaches zero, but never reaches it since there's no mechanism to guarantee all prisoners are picked.
Secondly, he can't live forever.
>>7689704
Exactly. But they're able to communicate before they make the choice.
>>7687435
top kek
