100 prisoners and a lightbulb

[Yakk]

Edit: Changed it to an easier version of the same puzzle. The original version is one of the varients. Also cleared up the fact that the switch and the lightbulb are connected.

"Take a look around you. I am going to lock up all 100 of you scum. Unless you can solve my puzzle, none of you will ever see the light of day, and none of you will ever see each other, ever again.

I am going to throw you all into cells. Every day, right after supper, I will randomly pick a prisoner, and take them to a room. In that room there is one lightbulb and one switch.

The only thing you will be permitted to do in the room is look at the lightbulb, and flip the switch that turns the lightbulb on and off if you want to.

Then you will be removed from the room, and returned to your cell, unless you claim that every single prisoner has been in the room.

If you make this claim, and you are right, you are all free to go.

If you make this claim, and you are wrong, you will all be killed.

Enjoy your last hour of contact with each other, scumbags. You get to spend the next hour thinking up the best plan your feeble minds are capable of."

Can the prisoners escape?

(Note: This is a reasonably famous puzzle. Many people will have the answer at their fingertips. I advise you to try solving it before reading the spoilers!)

Varients:

1. The prisoners cannot keep time. They cannot tell how many days it has been since the start of the test, or how many days it has been since they last where in the room.

2. The prisoners are robots. They can all follow the same algorithm, but they are not allowed to have a distinct prisoner before hand.

[ekim]

Yes, but you need the promise that "randomly pick" includes everyone, or just that at any given point in time, everyone will get called in at some point in the future.

The trick: assign someone the job of turning the light off, and everyone else the job of turning the light on.

[bbctol]

Do they have to flip the switch? Can they flip the switch as often as they like? Does the switch control the lightbulb? If so, I think I can figure this out.

[Lior]

Is the initial state of the lightbulb known?
What is the time frame for "every once in a while"? I have an idea, but if the time frame for each visit is long it might take them many many years.

[SittingInTheDark]

i think the 100 prisoners can only talk to each other together once for a strategy and then they can't communicate because if that weren't the case each one would just shout "i was in"

so here's the solution:

make one the master, only he may turn the switch on

if someone other goes in and
- the light is on he turns it off, but only if hasn't turned it off once, otherwise let it be

- the light is off let it be

each time the master turns the light on he counts one up
so if he counts to 99 all other were in there, but problem is what happens if light was off at beginning and master comes in first, would be a problem, or not?
no

each one may turn light off 2 times and master counts 2*99-1, so he might miss a second one from one person but that doesn't matter because everyone just has to be in at least once

[Castaway]

this is out there, but here goes something that I made up: So, the first person goes in and breaks the lightbulb into 100+ pieces, and puts one in a line. Then, every prisoner that goes in henceforth puts one more piece in the pile. If/when there are 100 shards in that line, then somebody makes the claim that everybody's been in there and voila! everyone wins!

[imMAW]

First, pick the smartest person in the group to decide how long it will take for the bulb to burn out. Divide this number by 100, and have everyone leave the bulb on for that amount of time. When the bulb burns out, pray that the persons estimate was right, and claim everyone has been in.

[Yakk]

Yes, you can't communicate other than through the lightbulb.

Yes, the switch controls the lightbulb.

You, and every other prisoner, will be shot if you violate the rules above.

Changed the puzzle to an easier version. Varient #1 is what I orginally posted.

this is out there, but here goes something that I made up: So, the first person goes in and breaks the lightbulb into 100+ pieces, and puts one in a line. Then, every prisoner that goes in henceforth puts one more piece in the pile. If/when there are 100 shards in that line, then somebody makes the claim that everybody's been in there and voila! everyone wins!

Congradulations, you where all shot. :)

[Cosmologicon]

Man, I always feel bad for the poor schlubs in this puzzle. Why don't you make it 20 prisoners instead of 100, and at least give them a chance of getting out before Andy Dufresne?

[Castaway]

if it helps, they aren't real prisoners. Our entire legal system is not based on Oedipus and The Sphynx.

[HenryS]

Man, I always feel bad for the poor schlubs in this puzzle. Why don't you make it 20 prisoners instead of 100, and at least give them a chance of getting out before Andy Dufresne?

As we noted in http://www.segerman.org/prisoners.pdf (lots of spoilers), there are strategies for 100 prisoners with expected times less than 4000 days, or about 11 years.

[edit]Even more fun variants: not only do they need to know that everyone else has been in the room, they also need to all have transmitted messages of arbitrary lengths to everyone else.

[skeptical scientist]

For variant 2:

Each prisoner follows the following strategy:
Put n=0

If you see the light off, and n is not -1, turn the light on, and increment n.

If you see the light on, and n is not -1, turn it off, and decrement n.

If n=100, report that all prisoners have been in the room.

Note that the sum, over all prisoners, of that prisoners value for n is always 0 (if the light is off) or 1 (if the light is on). So the only way that n can ever reach 100 is if all other prisoners have n=-1, so if the report is ever made, it will be correct, since n=0 until a prisoner has entered the room. So we need only show that a report will eventually be made.

Note further that if some prisoner's n reaches -1, that prisoner never does anything again, and their value stays constant at -1. If we call such a robot inactive, the amount of active robots is decreasing. Also, if n is not -1, then either n=99 (so the next time they go in the room, assuming the light is off, n will reach 100 and they will win), or there is another active robot. If there are two active robots, then depending on who is randomly picked to be in the room in what order, either can have their value of n go up or down. If the one with the lowest value is repeatedly sent in when the light is on, turns it off, and someone with the higher n value is then sent in and turns it on, that robot will become inactive, so every robot has a nonzero probability of becoming inactive in at most 2*n+1 days. Since we have an infinite number of days to work with, each robot will, with statistical certainty, eventually become inactive unless they are the only remaining active robot, so with a statistical certainty, the robots will win, assuming the choice of robot is truly random.

[Cosmologicon]

Man, I always feel bad for the poor schlubs in this puzzle. Why don't you make it 20 prisoners instead of 100, and at least give them a chance of getting out before Andy Dufresne?

As we noted in http://www.segerman.org/prisoners.pdf (lots of spoilers), there are strategies for 100 prisoners with expected times less than 4000 days, or about 11 years.

Yeah, if you run an optimization on the free parameters of a certain complicated model! These people have one hour to discuss it, and probably not a computer. I think the best they can hope for is a slight modification of Strategy 2, which (IIRC) gives them an expected time around 23 years.

[Captain_Thunder]

Assumming a different person is chosen each time to go into the room, all they would have to do is wait 100 days. The person who goes in after the 100th supper would be able to say that they are the last one to go in the room.

[skeptical scientist]

Assumming a different person is chosen each time to go into the room, all they would have to do is wait 100 days. The person who goes in after the 100th supper would be able to say that they are the last one to go in the room.

They're chosen randomly each time, so the probability of that happening is 100!/100^100, or about 1x10^-42. Congratulations, you're all dead.

[hermaj]

Yakk, did you use the search function at all before posting this thread? I cannot help but think that this puzzle has been presented before - and for that matter, more than once.


EDIT:
http://forums.xkcd.com/viewtopic.php?t=73

And a variant replacing switch with turning an object upside-down and right-side-up. http://forums.xkcd.com/viewtopic.php?t=514


I'll leave this open for now, I guess, unless another mod sees fit to close it. (These puzzles were presented a while back, I guess.) That said; for next time - search function, please.

[skeptical scientist]

Yeah, if you run an optimization on the free parameters of a certain complicated model! These people have one hour to discuss it, and probably not a computer. I think the best they can hope for is a slight modification of Strategy 2, which (IIRC) gives them an expected time around 23 years.

I imagine that beats the hell out of my variant 2 strategy, where you have to wait for a random walk in n variables to hit some hyperplane 100 different times. Fortunately robots generally have long lifespans.

[skeptical scientist]

Yakk, did you use the search function at all before posting this thread? I cannot help but think that this puzzle has been presented before - and for that matter, more than once.

If it's been posted long enough ago that people don't remember it, and many haven't seen it, what's the harm? It's not like people are reading through the puzzle archives, so sufficiently good puzzles merit reposting every now and then.

If people repost a puzzle from a few days ago or lower down the page, then that's kind of silly, but if someone posts a puzzle from a year ago, then the puzzle was probably interesting enough to be worth reposting.

[Belial]

You bump the previous thread, don't make a new one.

[HiEv]

As we noted in http://www.segerman.org/prisoners.pdf (lots of spoilers), there are strategies for 100 prisoners with expected times less than 4000 days, or about 11 years.

Yeah, if you run an optimization on the free parameters of a certain complicated model! These people have one hour to discuss it, and probably not a computer. I think the best they can hope for is a slight modification of Strategy 2, which (IIRC) gives them an expected time around 23 years.

Well, I guess it depends on whether you're willing to trade a shortened stay for a degree of uncertainty. I ran a few simulations of this situation 100,000 times, and the largest number of days I saw before all 100 prisoners had been to that room was 1,775 days (4 years and 314 days.)

Just to give you a few other sample statistics:

The smallest number of days I ever saw: 226 days
Average number of days needed: ~520 days
Median number of days needed: ~500 days
Number of days needed to be successful 99% of the time: ~915 days (~2.5 years)
Number of days needed to be successful 99.5% of the time: ~985 days (~2.7 years)

So, if they're willing to simply play the odds, they could get out in considerably less time.

[ptveite]

I've seen this before with 3 prisoners....much more humane, and the same basic answer.

[Yakk]

Sorry: the only lightbulb threads in the logic puzzles form where different.

The switch thread contains a very similar puzzle, except for the lack of a lightbulb, and the lack of varients. :/ Didn't find that one before I posted.

[Cosmologicon]

I ran a few simulations of this situation 100,000 times, and the largest number of days I saw before all 100 prisoners had been to that room was 1,775 days (4 years and 314 days.)

Just to give you a few other sample statistics:

The smallest number of days I ever saw: 226 days
Average number of days needed: ~520 days
Median number of days needed: ~500 days
Number of days needed to be successful 99% of the time: ~915 days (~2.5 years)
Number of days needed to be successful 99.5% of the time: ~985 days (~2.7 years)

So, if they're willing to simply play the odds, they could get out in considerably less time.

That's pretty good, but you can also do it by hand. For any large number of days N, the probability that you get them all in that much time can be estimated very well by 1 - 100(0.99^N). (The second-order term, which can be used as an upper-limit of the error on this estimate, is 4950(0.98^N).) So you can see that you have a 99999/100000 chance after 1604 days.

But of course this is a puzzle! When I'm telling it, I say the warden tells them, "If you make this claim, and you can prove that you are right, you are all free to go. If you make this claim, and you cannot prove it, you will all be killed."


I just realized that my favorite strategy (that takes about 23 years I think) works with Yakk's variant 2 but not with variant 1, that is, the prisoners must be able to keep time:

Basically it's just like SittingInTheDark's solution, except that the master is assigned at runtime. The first person who enters the room twice becomes the master, and gets a head start at counting everyone who's already been in the room once. In the first 100 days, nobody touches the light except that the master turns it off on her second visit. If someone enters the room in the first 100 days and it's on, they consider themselves counted, and if not, they just leave it alone. The master begins with the count set to the day before her second visit.

[Yakk]

My first solution to this was epicly inefficient:

Every prisoner gets a number, from 1 to 100.

They count days.

If DayNum != PrisonerNumber mod 100, they turn off the light. Otherwise they leave it alone.

Prisoner #1 turns on the light if it is off and it is Prisoner #1's day.

Prisoner #100 says "we have all been in the room" if he enters the room on his day and the light is on.

The expected wait time is rather ridiculous. :)

[skeptical scientist]

Basically it's just like SittingInTheDark's solution, except that the master is assigned at runtime. The first person who enters the room twice becomes the master, and gets a head start at counting everyone who's already been in the room once. In the first 100 days, nobody touches the light except that the master turns it off on her second visit. If someone enters the room in the first 100 days and it's on, they consider themselves counted, and if not, they just leave it alone. The master begins with the count set to the day before her second visit.

This doesn't seem like it works.

If the first person who enters twice is the master, they need to know they're the first person to enter twice. If we assume the light starts on, then how does someone know if the light has ever been turned off, assuming that the light is on when they enter?

Also, when I first read the puzzle, I could have sword it said the intervals were also random, so that's the version I solved (well, the variant where they all follow the same strategy, and the intervals are random.)

[Yakk]

Also, when I first read the puzzle, I could have sword it said the intervals were also random, so that's the version I solved (well, the variant where they all follow the same strategy, and the intervals are random.)

Edit:Changed it to an easier version of the same puzzle. The original version is one of the varients. Also cleared up the fact that the switch and the lightbulb are connected.

Yes, I changed it. I decided to post varients, and figured "why not post the easiest varient as the main puzzle".

I then documented my change. I source control gud!

[skeptical scientist]

My first solution to this was epicly inefficient:

The expected wait time is rather ridiculous.

Yes, an expected wait of 1,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000, 000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 times the estimated age of the universe is a little ridiculous, isn't it?

[Yakk]

googel^2 powa!

[Cosmologicon]

Hey skeptical scientist, I think my solution works fine. I think if you reread it you'll understand, but I can explain if you need. Just remember that it only works if the prisoners can keep track of time! Yours is the best solution I've seen that works under both variants 1 and 2 simultaneously.

[skeptical scientist]

Hey skeptical scientist, I think my solution works fine. I think if you reread it you'll understand, but I can explain if you need. Just remember that it only works if the prisoners can keep track of time! Yours is the best solution I've seen that works under both variants 1 and 2 simultaneously.

Nevermind, I missed the fact that nobody was allowed to touch the light in the first 100 days, except for the unique person who can turn it off.

[Cosmologicon]

Nobody turns on the light in the first 100 days.

[skeptical scientist]

Boo, you beat my rereading!

[Yakk]

Ah, but there is a refinement!

If P#N has entered the room on day X and seen the light on, he knows that every prisoner from P#1 to P#X-1 has been in the room.

From then on, he turns the light on on days 1 through X-1 (but not on day X).

If X=N, then he turns the light on on days 1 through X.

This changes the expected wait time quite considerably. :)

It takes 100 iterations for prisoner #1 to be on day 1.

This almost certainly then results in two people knowing about prisoner #1.

Knowledge that prisoner #1 has been in the room then grows hyperbolicly.

When either of the two people enters the room on day 1, they have a 98/100 chance of informing someone else that someone else has been in the room.

Then a 97/100. Then 96/100.

As #1 stays on more and more, #2 becomes more and more likely to see it. Once he leaves the light on, the number of people who know about #2 grows at a similar rate.

Not sure what the exact bound is, but is is much better than 100^100.

:)

[skeptical scientist]

Ah, but there is a refinement!

If P#N has entered the room on day X and seen the light on, he knows that every prisoner from P#1 to P#X-1 has been in the room.

From then on, he turns the light on on days 1 through X-1 (but not on day X).

If X=N, then he turns the light on on days 1 through X.

This changes the expected wait time quite considerably.

It takes 100 iterations for prisoner #1 to be on day 1.

This almost certainly then results in two people knowing about prisoner #1.

Knowledge that prisoner #1 has been in the room then grows hyperbolicly.

When either of the two people enters the room on day 1, they have a 98/100 chance of informing someone else that someone else has been in the room.

Then a 97/100. Then 96/100.

As #1 stays on more and more, #2 becomes more and more likely to see it. Once he leaves the light on, the number of people who know about #2 grows at a similar rate.

Not sure what the exact bound is, but is is much better than 100^100.

Yeah, uh, Yakk, I'm still not impressed by the efficiency of your algorithm. In a world where exptime algorithms are considered bad, an algorithm which takes o(n!) time is beyond silly, and even a huge improvement is still a really bad algorithm.

Edit: although I have to say, there is something appealing about tremendously bad algorithms. It's like the origin of Graham's number. A bad upper bound is boring, but a hideously bad upper bound is funny.

[fynch]

I've seen this before with 3 prisoners....much more humane, and the same basic answer.

Humane for us... or for the prisoners?

[Yakk]

*nod*: I'm well aware how horrid the algorithm, even with 'refinement', is.

I am curious how much faster the refinement makes it.

Knowledge of #1 gets spread at a rate of 100 * 100/N *(100-N)/100 assuming N people already know about #1.

This is bounded by 100^2.

If everyone knows about #1, then it takes roughly the same amount of time to find out about #2.

So this places an upper bound on the time it takes to solve the problem using my refinement at 100^3! A pretty good speedup from 100^100 eh?

As a bonus, individual prisoners can figure out the refinement independantly, after they leave and enter their rooms, and executing the refinement won't mess up the algorithm.

[skeptical scientist]

So this places an upper bound on the time it takes to solve the problem using my refinement at 100^3! A pretty good speedup from 100^100 eh?

Assuming you're right about this, you've brought the time down from an absurd power of 10 times the age of the universe to roughly 1/3 of the age of the universe. An impressive speed-up, to be sure, but still slightly impractical.

[Yakk]

100^3 is is 2700 years.

An eyeblink. :) I'm sorry if you exist in an 8000 year old universe, but I'm communicating to you from a far older one. Understanding the inter-universe communication method would make an interesting project. Are there any wormholes on your internet connection?

[skeptical scientist]

Oh, I was reading that as 10^(3!) because of the exclamation point.

[Nidht]

We can't assume the warden turns the light on or off at the end of each prisoner's session.

Each visitor to the room scratches a mark on the wall, someplace obscure, making it look inconspicuous. Then all it takes is counting.