[Guest]

I found this one on another website - it reminded me of so many other's we've seen here:

There are 100 prisoners in solitary cells. There's a central living room with one light bulb; this bulb is initially off. No prisoner can see the light bulb from his or her own cell. Everyday, the warden picks a prisoner equally at random, and that prisoner visits the living room. While there, the prisoner can toggle the bulb if he or she wishes. Also, the prisoner has the option of asserting that all 100 prisoners have been to the living room by now. If this assertion is false, all 100 prisoners are shot. However, if it is indeed true, all prisoners are set free and inducted into MENSA, since the world could always use more smart people. Thus, the assertion should only be made if the prisoner is 100% certain of its validity. The prisoners are allowed to get together one night in the courtyard, to discuss a plan. What plan should they agree on, so that eventually, someone will make a correct assertion?

[Guest]

That a particular inmate will ensure the light is turned on. Everyone else doesn't touch it. If they are all being chosen equally and daily from the first, they just need to wait until the person who turned it on gets back inside. He sees it's on and then can assert they have all been in the room.

[Guest]

umm, wouldn't that not work?

unless I'm just reading this wrong,

aren't they picked totally at random each day?

and no eliminations (i.e. if a person is picked do they not get picked again until everyone else has been picked, or is it possible to be picked 3-4 days, or even right after, you've allready been picked)

so the person who was designated to turn on he lightbulb could turn on the lightbulb, be picked again, say, 400 days later, assert that everyone has been in the room, but be wrong because, as a result of the randomness, someone was not picked?

and if there is eliminations, couldn't you just have everyone wait 100 days and on the 100th whoever is picked can assert everyone's been in there?

[bonanova]

For someone else to know that I've been there, I must leave evidence of my visit.

The only evidence I can leave is to turn the light on; so that's what I do.

Now suppose I am the prisoner who visits the room on Day 2 [and was not also the Day 1 visitor].

I find the light on, because it was turned on by the Day 1 visitor.

How can I leave evidence of my visit?

I can't, because the only action I can take is to turn the light off.

That would erase Day 1 visitor's evidence.

So I do nothing.

So the agreed way to signal that you've visited the room must be this:

When you are chosen to visit the bulb room,

if you find the bulb off,

turn it on;

else, do nothing.

The bulb is initially off.

After someone signals his visit by turning it on, how does it ever get off again?

One prisoner must be designated to turn the bulb off if he visits the room and finds it on.

Since the designated prisoner never turns the bulb on, no one else ever knows of his visits.

So he must be the person who determines when the other 99 have visited.

Finally, to be sure there is no double counting [due to multiple visits by any single prisoner],

the visit signal must be this:

When you visit the bulb room,

if you find the bulb off, and if and only if it's your first visit to the room,

turn it on;

else, do nothing.

When the designated prisoner has found the bulb on - and turned it off - 99 times,

he tells the warden that he and the 99 others have all visited the room.

[Guest]

warden picks a prisoner equally at random

It wouldn't be "equally" at random if they could get a double shot (the way I read it). Otherwise it would just be "randomly."

I assumed from the facts given that A) no prisioner would go twice before the others went once, and B) that nobody knows how long after the meeting occurs that the picks will start - i.e. no prisioner would have any way of knowing on what day the choices started. I suppose also, that we all assumed that the warden isn't messing with the bulb, and that the bulb wouldn't burn out before the counting is done.

[unreality]

It says that the warden does this EVERY DAY... so if it were only for 100 days it wouldnt be an ongoing thing like PDR implied, the prisoners would just wait til day 101 and then everyone has been there, guaranteed. You don't need to be in MENSA to figure that out. ;D

But there is obviously no starting day and no ending day, rereading the OP. The warden does this every day, each day, for as long as needed.

[Guest]

ohh, see

now it all makes sense

yes, I think that would work

but if they ARE chosen equally, and by equally, the OP means what writersblock says

then couldn't you just wait until it's your second time in the room?

[Guest]

disclaimer - I shamelessly copied the puzzle from elsewhere... <_<

that said- I interpreted "equally randomly" to be totally random. No way to know who's been picked or when. So that on day 2 everyone has a random chance to be picked - if even the person who went in the first day has a random chance to be picked on day 2 (or 3 or 4 etc.)

nothing was said about the bulb never burning out, so you'd have to assume it's a possibility.

For what it's worth - I think Bonova got it right. I wonder if there's any method that's faster though?

[unreality]

ohh, see

now it all makes sense

yes, I think that would work

but if they ARE chosen equally, and by equally, the OP means what writersblock says

then couldn't you just wait until it's your second time in the room?

I wasnt arguing against you, I was with you, and against writersblock, if you read my post. And it turns out we were right ;D

[bonanova]

I wonder if there's any method that's faster though?

Google informs that someone claims there are three solutions.

At least one of them could not be completed within the prisoners' lifetimes; but it wasn't described.

I conclude from that there may be a solution that's faster than the one I posted.

So I re-thought my post. At least from the way I've presented it, it seems unique.

That opinion, however, might be related to the fact that I'm quite certain that I have two simply incomparable grandchildren.

_{... as all grandparents seem to think ...}

[Guest]

I wasnt arguing against you, I was with you, and against writersblock, if you read my post. And it turns out we were right ;D

oh, didn't think you were anyhoo

[roolstar]

I don't think they all deserve to go to MENSA though...

All it took was one of hem to find the method...

Unless this is a clue that each one of them had some genius brain work to do to guess or to signal!

Edited January 17, 2008 by roolstar

[Guest]

Its kinda pretty simple.

They choose one leader who has to wait incessantly until his turn comes for a minimum of hundred times. Whenever he finds the bulb switched on, he switches it off. All the others have just one task.. whenever for the first time they find the bulb is switched off, they gotta turn it on and wait for the rest of their lives until eventually our leader toggles the bulb off exactly 100 times, and raises the MENSA alarm !!

P.S.: Any query would be greeted happily.

[Guest]

Its kinda pretty simple.

They choose one leader who has to wait incessantly until his turn comes for a minimum of hundred times. Whenever he finds the bulb switched on, he switches it off. All the others have just one task.. whenever for the first time they find the bulb is switched off, they gotta turn it on and wait for the rest of their lives until eventually our leader toggles the bulb off exactly 100 times, and raises the MENSA alarm !!

P.S.: Any query would be greeted happily.

He would only have to turn it off 99 times. Since he is the 100th person he would never turn it on just to turn it off.

[Guest]

For someone else to know that I've been there, I must leave evidence of my visit.

The only evidence I can leave is to turn the light on; so that's what I do.

Now suppose I am the prisoner who visits the room on Day 2 [and was not also the Day 1 visitor].

I find the light on, because it was turned on by the Day 1 visitor.

How can I leave evidence of my visit?

I can't, because the only action I can take is to turn the light off.

That would erase Day 1 visitor's evidence.

So I do nothing.

So the agreed way to signal that you've visited the room must be this:

When you are chosen to visit the bulb room,

if you find the bulb off,

turn it on;

else, do nothing.

The bulb is initially off.

After someone signals his visit by turning it on, how does it ever get off again?

One prisoner must be designated to turn the bulb off if he visits the room and finds it on.

Since the designated prisoner never turns the bulb on, no one else ever knows of his visits.

So he must be the person who determines when the other 99 have visited.

Finally, to be sure there is no double counting [due to multiple visits by any single prisoner],

the visit signal must be this:

When you visit the bulb room,

if you find the bulb off, and if and only if it's your first visit to the room,

turn it on;

else, do nothing.

When the designated prisoner has found the bulb on - and turned it off - 99 times,

he tells the warden that he and the 99 others have all visited the room.

Hello;

I'm a new visitor. I've read the enigma lately and i found a almost the same solution of bonanova's one. I think that there is a small mistake in your method:

You said: "When you visit the bulb room,

if you find the bulb off, and if and only if it's your first visit to the room,

turn it on;

else, do nothing."

Which means that some people will not have the chance to turn on the light because they visited the room and it was off.

I propose a small modification to your statememt:

When you visit the bulb room,

if you find the bulb off, and if and only if you have not turn on the light before,

turn it on;

else, do nothing.

Now i think the method works well.

I'm trying to prove that there is no faster method in the term of average. The average of our method is about 30 years

Thanks...

[Guest]

Hello;

I'm a new visitor. I've read the enigma lately and i found a almost the same solution of bonanova's one. I think that there is a small mistake in your method:

You said: "When you visit the bulb room,

if you find the bulb off, and if and only if it's your first visit to the room,

turn it on;

else, do nothing."

Which means that some people will not have the chance to turn on the light because they visited the room and it was off.

I propose a small modification to your statememt:

When you visit the bulb room,

if you find the bulb off, and if and only if you have not turn on the light before,

turn it on;

else, do nothing.

Now i think the method works well.

I'm trying to prove that there is no faster method in the term of average. The average of our method is about 30 years

Thanks...

I made a small mistake in my last reply.

Which means that some people will not have the chance to turn on the light because they visted the room for the first and the light was ONNN.

Thankx.

[bonanova]

You're right.

"if and only if it's your first visit to the room" is too broad.

Good catch. And ... welcome to the boards.

[Guest]

if they knew how much you have to turn the bulb for it to be turned fifty times before it comes out, then every day if it is your firsttime there you unscrew it, by the time fifty prisoners have come by the next person starts screwing it on, to tell everyone it is time to screw it on he makes a crac in the bulb, by the time everyone has gone through it is completely screwed on with a crack in it. so by the time everyone got to turn it once

[unreality]

if they knew how much you have to turn the bulb for it to be turned fifty times before it comes out

they don't

then every day if it is your firsttime there you unscrew it, by the time fifty prisoners have come by the next person starts screwing it on

You mean when it has been screwed off by 50 prisoners? How does each prisoner know the exact amount needed to spin it? Well they don't... as the OP said. And they can't change the lightbulb or leave any mark of their passing... otherwise they could just scratch the bulb on their first visit, and if they count at least 99 scratches (100 if they have been there before) then they can just tell the warden. But they cant

to tell everyone it is time to screw it on he makes a crac in the bulb, by the time everyone has gone through it is completely screwed on with a crack in it. so by the time everyone got to turn it once

Good idea.... except you cannot touch the bulb, or anything else, except flick the ON/OFF switch. You cannot leave marks of your passing.... otherwise it would be very easy, if you CAN scratch the bulb like you did, you can get rid of the fifty-twists thing and just have each person scratch the bulb on their FIRST AND ONLY FIRST visit, and when someone counts 99 (if this is their first visit) or 100 (a later visit so they've already scratched), everyone has been there at least once. Easy. That's why the OP said you cant do stuff like that

[Guest]

I explained this one to my wife and she got it straight away (before I did ). She explains it nicely:

One prisoner agrees to be the counter. The counter always leaves the light on when they leave, to say I'm ready to take a message. Everyone else is able to leave a message by turning the light off. (If you come in and the light is off, you don't have the option of leaving a message.) Make sure you leave a message to announce your first visit at your first opportunity, and announce it only once. Once the counter has received 99 messages, that means there have been 99 first visits plus their own, so they can safely make the assertion.

You can shave off a few days by making everyone agree that whoever happens to be the visitor on the first night gets the job of counter.

[Guest]

And now here's my contribution.

The following statements are true:

The first visit will definately be a first-visit.

The second visit will probably be a first-visit (let's face it).

It wouldn't be surprising if the first 50 visits were first-visits.

So the prisoners could work from this false assumption: That the first 50 visits will be first-visits.

And they could agree to leave the light off for the first 50 days, until that assumption fails.

The first person to visit for a second time within the first 50 days falsifies the assumption. They switch the light on to let people know, and they get the job of 'counter'. The good news is that they can start the count at (day#-1). That is, if it is the 34th day, they can start the counter at 33. The light will remain on until the end of the 50 days so that people know the assumption has failed (so that anyone else who comes back a second time knows that they are not the first to do so). After the 50 days are up, the counter starts their job, and the prisoners proceed as per the other solutions.

This works even in special cases like when the assumption turns out to be true (if all 50 visits are first-visits, the 51st visitor sees the light off and gets the job of counter, starting the count at 50). Also, there is no problem switching from the first phase to the second (i've checked).

This could shave decades off the total time.

Bonus points if you can figure out what the optimal assumption is (is 50 days really a good number? why not 30? or 100?), and how much time on average it would save the prisoners.

[roolstar]

You can shave off a few days by making everyone agree that whoever happens to be the visitor on the first night gets the job of counter.

Actually you can't shave any days with this agreement: in fact this may screw up the whole system!!

According to your method, any prisoner going for the first time into the room cannot tell if he's the first one to go in or if anybody was there before him.

Let's say a prisoner came into the room for the first time (HIS first time) and he finds the light off, this may be because:

A - He really is the FIRST VISITOR and thus needs to take the role of the counter.

B - Two guys came in before he did, the first one (counter) turned the lights on, and the second guy turned the lights off as he was supposed to do, just before our prisoner got in.

So the only way here is to assign the counter from the beginning!

So, your method is a bit different than Bonanova's (according to him the assigned counter turns the light off not on), and your method actually may take even a bit longer: in your method, the counting starts AFTER the COUNTER visits the room for the first time (for him), and before he does, all the visitors will find the lights off and have to wait. While for Bonanova, the first guy in (especially if not the counter) will immediately start the signaling.

Thinking about this a bit harder and I find that there is only one possibility where YOUR method becomes shorter that Bonanova's:

If the first VISITOR of the room is the counter himself, according to Bonanova he will have to wait till his next visit to receive the first signal. but of course this has a probability of 1/100 to happen, and may make your way about 100 days shorter.

But in 99/100 of the cases, Bonanova's method is around 100 days shorter.

Edited January 23, 2008 by roolstar

[roolstar]

Bonus points if you can figure out what the optimal assumption is (is 50 days really a good number? why not 30? or 100?), and how much time on average it would save the prisoners.

According to your method, the following is true:

1 - The higher we can start the counter and the more time it will save us. Actually every +1 counter will save us about 100 days (assuming the longest rotation)

2 - The higher the number of agreed upon days (your example was 50) and the longer we need to wait before counting. Every +1 day makes us lose 1 day!

3 - If the assumption survives past day 50 (or any preset day), this means we lost some opportunity of giving the first value of the counter a bigger value.

4 - It's plain stupid to set the number of days to more that 100.

This said, we can clearly see that the possibility of getting +1 counter offsets very easily the risk of losing a couple of preset days.

I will have to say that the number of preset days should be 100! (and not 99)

Why 100? Well, we can hope for the possibility of everybody visiting the room once for the first 100 days, and the visitor on the day 101, seeing the light still of, will declare that everybody had already visited the room! I would choose to wait an extra day to possibly save 100!

But hey, that's just me!

Edited January 23, 2008 by roolstar

[roolstar]

Now as for how long will this save us?

The formula may look a bit like:

AVERAGE SAVED TIME = COUNTER VALUE x 100 - 98*

* 98 because the first 2 days are lost either way since we cannot set the counter to less than 2.

Remember that you have to wait till 100 before you declare freedom and not only to 99!

[Guest]

Actually you can't shave any days with this agreement: in fact this may screw up the whole system!!

According to your method, any prisoner going for the first time into the room cannot tell if he's the first one to go in or if anybody was there before him.

No real problem here. The prisoners agree on a start date for the plan (say, the first night after the big meeting), so that the first person knows they are the first person. I should have been explicit, sorry.

[Guest]

I will have to say that the number of preset days should be 100!

Yes, it seems worthwhile investing a mere 100 days to potentially save in the order of 100*100 days. You would only save one day by knocking it back to 99, and you would loose the, albeit very very slim, chance of saving a whole ~100 days. Sounds like it could be worth it to let phase1 go for 100 days. (Sounds.)

Edited January 23, 2008 by oranfry