Riddle: 100 Prisoners and a lightbulb

Factual Questions
21

Another possible way to do this is agree to abandon some unidentifiable portion of the first one hundred days in order to increase the odds of counting a large number of visits in the first round. (very likely, and more likely that round than any other)

We all count days, and no one turns the switch, unless it is his second visit. In that case, the first second time visitor becomes the counter, and turns on the light, He knows that the count is equal to the number of the day. He leaves the light on. No one changes the light for any reason until the one hundredth day, and that person turns the light out, without regard to whether he has visited before.

If the one hundred and first day visitor finds the light out, he demands freedom. (he will have already visited of course) If he is the counter, and the light is on, he turns it off, but does not increment the count, since it might be still on from when he turned it on. After that, everyone continues to turn on the light if they can, once, and not again. The counter turns the light out, and increments the count, each time he comes in.

This is a much faster method, unless the first repeat visitor comes early.

Tris

22

Whew, equal to one less than the day, of course, he was here already. Damn off by one error will get you every time.

23

Here’s another refinement which may or may not assist, but odds on it would.

At the meeting, instead of choosing a designated person as such, it is agreed that the person who comes into the room on day X is the designated person.

Up to day X, people coming into the room only turn it on if they have been in the room before. If on day X the person coming into the room (who is now the designated person) finds the light on, then he just counts one. But if he discovers the light off, then he can count off X-1 persons as having been in the room for the first time. Either way, after day X the scheme changes to the standard solution proposed as above.

Obviously, it would take some pretty tricky calculations to decide when the odds favour “day X” to be. The earlier you set it the more chance that the light will not be on thereby providing at least some useful information, the later you leave it the more chance you get nothing out of the scheme because someone will have repeated, but the more information you get out of the scheme if no one has.

If you set it for example at day 10, I think the odds would be reasonable that on day 10 the designated person could count off 9 people at one swoop.

24

Nah, that wouldn’t help - if you set X to 10, there would be a 69% chance that you could count off 9 people, and a 31% chance that you could only count 1 (or 2 if prisoner X had visited before). That would give you an average head start of (a little over) 9x0.69 + 1x0.31 = 6.52, although you would also save 90 days over Tris’s method. The best you could do is X=11, which would give a head start of 6.7.

Tris’s method would give an average head start of 12, which is a lot better than 6.7 even with the extra 89 days.

25

It doesn’t say the prisoners can’t see the light from the light bulb, only that they can’t see the bulb itself, in which case the problem becomes a lot easier.

26

SORRY!

I thought that they could see the light from their cells. I misread the question. I told you it sounded too simple…

27

Hmm…Lemme think about this for awhile, but I suggest that we have at least one extra variable the prisoners can keep track of (whether it helps or not is another issue): which day they’re on.
So the prisoners obviously know that the first possibility in which all 100 prisoners have visited the room is day 100.

Perhaps there’s a way we can incorporate day of incarceration and status of light bulb into the equation. The simple way to start is:

  1. First person turns light on
  2. If person has been in room before, turns light off
  3. Everybody else leaves light as is.

On day 100, if the light is on, then it means everybody’s been there before. Chances are, though, the light will be off. At this point, I suspect there may be a way to add this information to the date tally and somehow arrive at a quicker solution. Or maybe not. Just trying to add an additional variable which we can somehow incorporate into a more elegant solution.

Or the prisoner can just yell real loudly “YO GUYS! THIS IS MY FIRST TIME IN THIS ROOM” and everyone else just keeps tally. :slight_smile:

28

This is a flawed modification to Usram’s modification to Triskadecamus’ method, but I’ll post it anyway; maybe someone else can figure out how to fix it.

For the first 200 days, follow this pattern: First day, turn light on. Afterwards, if light is on and it’s your third time, turn it off, and set count equal to day. You are now the counter. If light is off, leave it off.

Afterwards, if you’ve never turned the light on, turn it on if its off. If you turned it on twice during the first 200 days, and the light is on, turn it off. Afterwards, proceed as if you’ve only turned the light on once (i.e., you only turn the light off once, to make up for having turned it on twice). Counter will turn the light off if its on, and increment count. When counter gets to 100, ask for freedom.

Unfortunately, there’s a possibility one of the people who turned the light on twice won’t get a chance to turn it off before 99 people have turned it on at least once, and if that last person never visited the room, you’re all dead.

Over 1000 runs, I got an average of 6619 days, with a min of 1977 and a max of 12,195 (and no deaths :slight_smile: ).

29

Here was my solution:

The first prisoner turns the light on and selects an area on the floor and wall where he/she scratches in a rectangle big enough to hold the numbers 1 through 100. The he puts in the number 1.

No one turns the light off.
As prisoners are called in, they will write the next number if they are a newbe. Otherwise, they do nothing.

When a newbe eventually comes in who sees all the numbers up through 99, he knows that he is the 100th distinct visitor in the room, so he can assert the claim that all 100 prisoners have been to the living room.

(Actually, this solution really has nothing to do with the status of the light bulb, they could do it in total darkness, because the technique would still work if the new visitors just made a deep scratch to tally their first visit. The prisoners could just feel the tally marks and count them. The one who feels (and counts) 99 scratches knows he is the 100th).

30

AV8R, you can’t assume that they can write on the walls, or communicate with each other, other than through the light bulb’s on/off status. Otherwise, it’s too easy. You might as well assume that they can intially make their meeting in the living room, and declare they’ve all been there!

31

Quoth Triskadecamus:

There’s something wrong here. You say that Visitor #100 always turns off the light, and then if 101 sees it off, he demands freedom. By this plan, won’t Mr. 101 always demand freedom? That sounds mighty non-optimal to me.

32

There’s no guarantee every one of the prisoners will EVER be selected. I will presume it’s better to have some finality – either release us or execute us if the odds are good enough for release.

My suboptimal method. Each prisoner keeps track of the day number and his own private “count”. Each time he visits he increases the count by his own visit and also adds additional first visits indicated by the light. Ahead of time, all prisoners agree to the “count” that will trigger the end.

There will be “queues”, say 20. If its the prisoners second or later visit, he makes sure the light is on and it will remain on until the 20th, who will then turn it on or off, depending if its HIS first visit.

The first cycle, the first 15 may be all unique visits, so each(till the light is on) will add between 1 and 15 to his own count. Once the light is on, later visitors in the queue will only add themselves.So forth. The first and 20th in each cycle will always choose on(have visited) or off(first visit). The 20th will always tell the first in the next queue whether he’s visited, etc.

At some predetermined cycle number, only the first or 20th will turn the light on/off depending on their visit, but any first visitor will turn the light off. Every later visitor in the queue will know by the light being off, a new first time visitor has occurred, therefore add one(plus himself) to his private “count.”

If the count trigger is “100”, then the absolute maximum visits will be about 9900 plus 1.

33

Yeah, I got it a little off Chronos,

First one hundred days.

No one turns on the light unless he is entering the room for the second time, and the light is off. The first prisoner who enters for the second time turns on the light, and counts the people who came in before his second visit. (day number, minus one) He now designates himself the official counter. The light is now on. On the rest of the first 99 days, no one turns off the light. On the one hundredth day, the person entering the room turns the light off. (if it is still off, that means no one has entered twice in one hundred days, and that person demands freedom. Unlikely, but possible, and you would hate to miss that one!)

All days after the first one hundred. If you entered the room during the first one hundred days, and before the light was turned on, you are already counted. Do not turn on the light. Do nothing. If you never entered the room until after the light was on during the first one hundred days, you are not counted. You turn on the light if it is off, and are then counted, and do not turn it on again. If you never entered the room at all during the first one hundred days, you are not counted, you turn on the light the first time it is off when you enter, and do not turn it on thereafter. If you are the counter, if the light is on, you turn it off, and increment the count. When the count is 100, you demand freedom.

I think I have it right this time.

The person who enters on the one hundredth day turns the light off until after the 99th day. After that that, only the counter turns it off.

The counter is the first one to turn the light on after that he turns it off, if it is on, and leaves it off if it is off. Turning it off increments the count.

People who came into the room with the light off during the first one hundred days, do not turn the light on ever. (Except the counter, who came into the dark room twice in the first one hundred days.) Everyone else turns on the light the first time they can, and do not turn it on thereafter.

Check it, please, I don’t want to get us all killed.

Tris