100 Prisoners and a light switch [solutions]

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

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

100 Prisoners and a light switch [solutions]

Postby UltramaticOrange » Thu Oct 11, 2007 9:00 pm UTC

Here's a trimmed version of a solution. Find the originalhere.

Alice counts the times she finds the light on, and ensures that it is always off when she leaves the room. Everyone else turns on the light the first time they find it off, and then never touches it again. This way, between visits of Alice, at most one prisoner will turn on the light, and no prisoner turns it on more than once. Therefore the number of times Alice finds the light on is no more than the number of different prisoners that have entered the room. Each prisoner knows he has been counted once he has turned the light on, since he is the only one who touched the switch since Alice last visited. When Alice counts to n-1, she knows everyone has visited the room.

I wrote a program to simulate this solution. Feel free to check it for bugs (this is the first bit of C++ I've written in about 2yrs). You may note some incomplete functions ... this is still a work in progress. Compiles with Visual C++ 6 (blech) fellow GNU-ers will need to make some minor changes to get it to compile.

User avatar
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 [solutions]

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

locked cause its been done three times before. once is enough.
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 12 guests