100 Prisoners and a light switch

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

UltramaticOrange
Posts: 45
Joined: Wed May 30, 2007 3:31 am UTC
Contact:

100 Prisoners and a light switch

Postby UltramaticOrange » Thu Oct 11, 2007 8:41 pm UTC

Some co-workers and I were discussing logic problems at work the other day and in the process of looking for details on one, we ran across one none of us had seen before. The original post is here (2nd post contains answer and a more thorough version of the answer is on page 3).

Q: How can the prisoners tell, with certainty, that all 100 of them have visited the central living room with the light bulb.

The riddle: 100 prisoners are in solitary cells, unable to see, speak or communicate in any way from those solitary cells with each other. There's a central living room with one light bulb; the bulb is initially off. No prisoner can see the light bulb from his own cell. Everyday, 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 he or she wishes. Also, the prisoner has the option of asserting the claim that all 100 prisoners have been to the living room. If this assertion is false (that is, some prisoners still haven't been to the living room), all 100 prisoners will be shot for their stupidity. However, if it is indeed true, all prisoners are set free. Thus, the assertion should only be made if the prisoner is 100% certain of its validity.

Before the random picking begins, the prisoners are allowed to get together to discuss a plan. So ---- what plan should they agree on, so that eventually, someone will make a correct assertion?
Image

musthavebeenmykarma
Posts: 42
Joined: Fri Oct 05, 2007 6:02 am UTC

Re: 100 Prisoners and a light switch

Postby musthavebeenmykarma » Thu Oct 11, 2007 9:03 pm UTC

two questions:

Can the same prisoner be picked twice?

When all 100 prisoners have entered the room, does prisoner # 100 have to guess correctly or does the game go on until someone guesses?
Newpages: 250/2,3?? (~10%}

Blitz for it...

User avatar
Torn Apart By Dingos
Posts: 817
Joined: Thu Aug 03, 2006 2:27 am UTC

Re: 100 Prisoners and a light switch

Postby Torn Apart By Dingos » Thu Oct 11, 2007 9:51 pm UTC

This puzzle has been on the forum before. The same solution was found.

Buttons
Posts: 858
Joined: Wed May 02, 2007 3:27 pm UTC
Location: Somerville

Re: 100 Prisoners and a light switch

Postby Buttons » Thu Oct 11, 2007 10:55 pm UTC

In fact, a regular on this forum wrote a reasonably well-known academic paper on the problem. I think it's in the What's Your Erdõs Number thread in the Math forum.

UltramaticOrange
Posts: 45
Joined: Wed May 30, 2007 3:31 am UTC
Contact:

Re: 100 Prisoners and a light switch

Postby UltramaticOrange » Fri Oct 12, 2007 1:58 am UTC

two questions:

Can the same prisoner be picked twice?

When all 100 prisoners have entered the room, does prisoner # 100 have to guess correctly or does the game go on until someone guesses?
1. Yup
2. The person has to guess correctly or everyone is sentenced to death.

This puzzle has been on the forum before. The same solution was found.

In fact, a regular on this forum wrote a reasonably well-known academic paper on the problem. I think it's in the What's Your Erdõs Number thread in the Math forum.
Damn. I did a search on the word "prisoner" but I guess it wasn't enough ... or I just missed it. If anyone happens to find the original, could you post a link to it? I'd like to read through the thread.
Image

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: 100 Prisoners and a light switch

Postby jestingrabbit » Fri Oct 12, 2007 3:15 am UTC

here is one such thread

viewtopic.php?f=3&t=4100

and here is the post with the link to the good article

viewtopic.php?p=87536#p87536

here are some other copies of the same puzzle

viewtopic.php?t=73

viewtopic.php?t=514

This is getting the lock on both threads. If you want to talk about it use one of the threads that already exists.

PS the first link here was on the second page of the 'prisoner' search results (so long as you restricted to LP), and the rest were in that thread.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 13 guests