Brainteaser

[MikeMike]

Originally posted by: Zoblefu
That was exactly what I was thinking, but this doesn't work if you don't know the initial state of the light....

yea it does, just always have a first timer flip the position of the light, otherwise leave it the same

basically whoever goes in first, is the one who keeps turning it on/off.

 

[stan394]

Answer:

During the discussion phase, the 30 prisoners designated one as the Counter.

For a non-Counter prisoner, he turned on the light bulb, if
- the light bulb is off, and
- and he has never turned on the light bulb before, and
- he did this only once, ever

For the Counter, he turned off the light bulb, whenever
- he sees that the light bulb is on.

The Counter can go talk to the warden once he turned off the light bulb 29 times.

EDIT:

For a more fault tolerant solution, each non-Counter prisoner turned on the light bulb twice only when it's off. The Counter goes talk to the warden after he turned off the light the 59th time.

 

[Zoblefu]

If you knew the light was going to be off at the very beginning.... (or on, and you can reverse it)

Only one guy can ever turn the light off. He is counting how many times he turns the light off. Everyone else only turns the light on during their first visit.

When the one counting turns the light off the 30th time (or well, he sees the light on for the 30th time) then he knows everyone has been in there.

(or 29 times, rather, since you don't count the counter as one who turns the light on)

 

[YOyoYOhowsDAjello]

Originally posted by: Zoblefu
If you knew the light was going to be off at the very beginning.... (or on, and you can reverse it)

Only one guy can ever turn the light off. He is counting how many times he turns the light off. Everyone else only turns the light on during their first visit.

When the one counting turns the light off the 30th time (or well, he sees the light on for the 30th time) then he knows everyone has been in there.

(or 29 times, rather, since you don't count the counter as one who turns the light on)

But if your first visit is before the counter guy gets into the room, how does that work?

 

[Zoblefu]

If the light starts off, though, the first person in will turn it on (he doesn't know if it started off, or if the counter has turned it off)

Then when the counter goes in for the first time and the light is on, he doesn't know if he should count it as a person who turned it on (and therefore won't turn it on again) or if it started on!

This is why I asked if you knew you were the first to the room. Then they could agree that the first to the room was the counter... but that doesn't work either.

 

[stan394]

For a more fault tolerant solution, each non-Counter prisoner turned on the light bulb twice only when it's off. The Counter goes talk to the warden after he turned off the light the 59th time.

 

[stan394]

Originally posted by: YOyoYOhowsDAjello

Originally posted by: Zoblefu
If you knew the light was going to be off at the very beginning.... (or on, and you can reverse it)

Only one guy can ever turn the light off. He is counting how many times he turns the light off. Everyone else only turns the light on during their first visit.

When the one counting turns the light off the 30th time (or well, he sees the light on for the 30th time) then he knows everyone has been in there.

(or 29 times, rather, since you don't count the counter as one who turns the light on)

But if your first visit is before the counter guy gets into the room, how does that work?

you don't do anything. you wait until the light is off. then you turn it on. but you only got to do this twice, ever.

 

[YOyoYOhowsDAjello]

Originally posted by: stan394
Answer:

During the discussion phase, the 30 prisoners designated one as the Counter.

For a non-Counter prisoner, he turned on the light bulb, if
- the light bulb is off, and
- and he has never turned on the light bulb before, and
- he did this only once, ever

For the Counter, he turned off the light bulb, whenever
- he sees that the light bulb is on.

The Counter can go talk to the warden once he turned off the light bulb 29 times.

EDIT:

For a more fault tolerant solution, each non-Counter prisoner turned on the light bulb twice only when it's off. The Counter goes talk to the warden after he turned off the light the 59th time.

Did you make up this solution or is this a real problem?

 

[Zoblefu]

Originally posted by: stan394
For a more fault tolerant solution, each non-Counter prisoner turned on the light bulb twice only when it's off. The Counter goes talk to the warden after he turned off the light the 59th time.

You will still be off by one if the light starts on. The counter doesn't know to count it or not during his first visit.

 

[stan394]

Originally posted by: YOyoYOhowsDAjello

Originally posted by: stan394
Answer:

During the discussion phase, the 30 prisoners designated one as the Counter.

For a non-Counter prisoner, he turned on the light bulb, if
- the light bulb is off, and
- and he has never turned on the light bulb before, and
- he did this only once, ever

For the Counter, he turned off the light bulb, whenever
- he sees that the light bulb is on.

The Counter can go talk to the warden once he turned off the light bulb 29 times.

EDIT:

For a more fault tolerant solution, each non-Counter prisoner turned on the light bulb twice only when it's off. The Counter goes talk to the warden after he turned off the light the 59th time.

Did you make up this solution or is this a real problem?

A friend asked me this question. He knows the answer.

 

[stan394]

Originally posted by: Zoblefu

Originally posted by: stan394
For a more fault tolerant solution, each non-Counter prisoner turned on the light bulb twice only when it's off. The Counter goes talk to the warden after he turned off the light the 59th time.

You will still be off by one if the light starts on. The counter doesn't know to count it or not during his first visit.

hm sorry, actually the Counter only needs to turn off the light 58 times.

After he turns off the light 58 times, he knows that all 29 have already been in the room because if not, the light can only be on 57 times at most (28*2 + 1 initial).

 

[YOyoYOhowsDAjello]

Can you break down the solution like this?

I am not the "counter"
What do I do?

I go in on my first time

1. The light is off
A Turn it on
B Leave it off

2. The light is on
A Leave it on
B Turn it off

 

[stan394]

Originally posted by: YOyoYOhowsDAjello
Can you break down the solution like this?

I am not the "counter"
What do I do?

I go in on my first time

1. The light is off
A Turn it on
B Leave it off

2. The light is on
A Leave it on
B Turn it off

If you are not the counter person, it doesn't matter what you do when you go in the first time. Your strategy should be the same every time you go into the room.

Whenever you go into the room, you turn on the light only if the light is off and you have not turned on the light twice, total. You only got to turn on the light twice, over the course of the game.

 

[eakers]

we had this question in first year programming

 

[stan394]

Originally posted by: eakers
we had this question in first year programming

this is more like grad level Distributed Algorithm

 

[YOyoYOhowsDAjello]

Oh, I thought you had to tell the warden as soon as the condition was satisfied.

 

[Ready]

This is so easy. One prisoner goes in, turns off the light, kill the warden, and free all the prisoners!

 

[stan394]

Originally posted by: Ready
This is so easy. One prisoner goes in, turns off the light, kill the warden, and free all the prisoners!

heh heh :evil: