Fog Creek Software
Discussion Board

Swithces Puzzle - Hint needed

Is there a solution where the prisoners can be certain?

My initial thoughts were that they agree to cycle the switches as follows:

A-On & B-Off -> A-On & B-On -> A-Off & B-On -> A-Off & B-Off -> A-On & B-Off ....

Now each time a prisoner revisits the room, they can get an idea of the number of people that have visited the room. If they leave it in the A-On & B-Off state and return to find it in  A-On & B-On state then they can be sure one person has visited the room (obviously it could actually be more 5, 9, 13 .. but they know at least that its 1). Each individual can then sum up the minimum number of visitors the room has had.

They could all agree on a number at which point they will take the risk and guess that everybody has visited the room.

Saturday, March 29, 2003

...except that each prisoner is only allowed to move _one_ of the switches.

Saturday, March 29, 2003

A-On & B-Off -> A-On & B-On -> A-Off & B-On -> A-Off & B-Off -> A-On & B-Off ....

They do only move one switch.

E.g  if the find it in the A-Off & B-On state they switch B to Off to get A-Off & B-Off.

Saturday, March 29, 2003

Here's a better hint (other than going to car talk and looking up the answer):

Use one of the prisoners as a counter.

Saturday, March 29, 2003

Simple: every prisoner leaves one of his socks, and just one, the first time he enters the room. :)

Requirements said nothing about sock counting.

(am I even supposed to post answers here?)

Rob Kaper
Saturday, March 29, 2003

Whoever goes the 23th time first announces it ?

Sunday, March 30, 2003

Stamp the wall with your shoe when you go there the first time. When there are 23 footprints on the wall, you know...

Twisted Brian
Friday, May 2, 2003

one possible solution could be for the prisoners to communicate via even or odd numbers (the positions of the switches can be interpreted as bits which could be in 4 positions - 00, 01, 10, 11).

However, since only two switches are available, only one person can keep the score.

The way it could work is the following

If you are the score keeper
    turn the switch position from even to odd if it is even
    leave the switch position to odd if it is already odd

If you are a non-score keeper
    turn the switch position to even if this is your first visit    when the switch position is already at odd
    leave the switch position at even if it is already even

Please note that even if this is the first visit and the switch is already ON, there is still a need to indicate to the score keeper to increment the counter. So the rule to be discussed during the strategy session is the following

Only the score keeper can change the state from even to odd. If the switch is even, the score keeper will increment his counter by 1.

All the others can change the state from odd to even only if the position is odd and this is their first visist after the position is already odd. This is to differentiate between cases where multiple prisoners could all visit for the first time one after the other.

Assuming a random distribution, after a certain number of visits, if the score keepers counter reads 22, that means that everyone including himself has visited at least once.

sangeeth ram
Wednesday, May 7, 2003

*  Recent Topics

*  Fog Creek Home