1. A Simple Logic Puzzle....

Hi Friends,

100 prisoners are locked up in individual cells, unable to see, speak or communicate in any way with each other.

There is a central living room with a single light bulb, the bulb is initially off and no prisoner can see the light bulb from their own cell.

Every day, the warden picks a prisoner at random, and that prisoner goes to the central living room.

While there, the prisoner can toggle the bulb if they wish (off to on, or on to off).

At any point, any prisoner can claim that all 100 prisoners have been to the living room. If they are wrong then all 100 prisoners will locked up forever! However, if they are correct all of the prisoners are set free.

Before the random picking begins, the prisoners are allowed to discuss a plan.

Then guys.......

The Question........

What is their best plan to determine when all 100 prisoners have visited the living room?

Thanks,
Riju

2. Re: A Simple Logic Puzzle....

A sufficient condition for all of the 100 prisoners having been to the CLR would be that 100 days go by without any prisoner having been there twice. This results in the following plan for a prisoner visiting the CLR:
- If the light is off, turn it on and start counting the days, this day being day zero.
- If the light is on, and your counter is 0, start counting the days, this day being day zero.
- If the light is on, and your counter is greater than zero, but < 100, turn the light off and stop counting days.
- If the light is on, and your counter is 100: inform warden that the liberating condition has been met!
- If the light is on, and your counter is >100, reset the counter to 0, but keep counting.

On a day where you don't visit CRL and are counting days, then increment the counter.

For a truly random selection sequence of prisoners, chances for success are extremely small!

3. Re: A Simple Logic Puzzle....

Even for a truly random selection sequence of prisoners, the chance for success is 100&#37; using the below approach. However, the time required is very very very long. Getting freed in a long time is better than getting killed.
One of the 100 prisoners can be named/nominated for counting the "ON"ed states of the bulb whenever he gets his turn to visit the CLR. Other prisoners can switched ON the bulb only when they visit the CLR for the first time and are not supposed to change the state of the bulb during their sub-sequent visits. The counting prisoner must add 1 to his total if the bulb is ON during his visit (as mentioned above) and then "OFF" the bulb. As soon as he counts 99, he must go to the warden and claim that all the 100 prisoners have visited atleast once.

4.

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•