Prisoner dilemma

[borisp]

Ok, so this isn't THE prisoner dilemma, but it is a problem in which prisoners face a dilemma. I got this from my friend, who was asked this problem in some job interview.

You and 30 other prisoners (the # doesn't matter) are being held in a common jail cell. You know that shortly you will all be taken to solitary confinement, at which point you will no longer be able to communicate, but you are free to discuss strategy now.

You also know that after you are separated, the guards will sporadically take individuals to a room with two switches, labeled "switch A" and "switch B," and that each switch is either in the "up" or "down" position, and that right now they are both down. When you are taken to this room, you have to switch exactly one of the switches, and then you go back to solitary.

You don't know the order that the guards will take you; you might visit the room 10 times in a row while everyone else sits in their cell, or you might sit in your cell while the guards cycle through everyone else 1000 times, etc. (I.e., assume the guards act randomly in choosing who visits the room next.)

Your task as a group is to at some point have someone declare factually that every prisoner has visited the room. For the sake of argument, say that if someone guesses that everyone has visited, and that person is wrong, then you all are put to death, whereas if that person is correct, then you all go free.

So what is your group's strategy?

[PairTheBoard]

We looked at this problem here some months ago. I could not figure it out then. I remember the solution was pretty cool, but I can't remember it now. I will pretend I've never seen the solution and try to figure it out again, with a little help from a hazy memory.

PairTheBoard

[borisp]

Hint (from the interview) in white:

<font color="white"> What if there were only one switch, and you have the option to do nothing when you enter the room? </font>

[MaxWeiss]

How would that help in knowing if others have visited??? If somebody comes a second time, say before somebody else comes the first time, does he flip it then? If not, then there's nothing you can tell. And if you, you can only tell that a person has been there at least twice; you cannot infer that everybody has been there unless you know the guards are doing one at a time until everybody goes there. How does your hint help??

[borisp]

You are describing the failure of your imagination as if it were an insight into someone else's mistake.

[PairTheBoard]

I remember from seeing the solution before that it uses the 2 switches essentially like in your hint. But I can't remember how the solution goes. I seem to be struggling with the same lines of attack which IIRC were missing the right insight when I tried to solve it before.

We've looked at several versions of the Monks with Blue Dots on their Foreheads type problems here. Where a kind of nested logic allows a conclusion to be drawn by the participants. I'm thinking something like that might be used here, but I don't see how.

Also, there might be some kind of "Existence" proof by induction where the prisoner who ends up "knowing" is not identified but just proved to exist. It seems like the best that can be done is to have each person Flick the non-noise switch exactly once. Then argue what the N people know after the first N Flicks implies about what the N+1 people know after the first N+1 Flicks.

But as I recall, the solution I saw was so Slick that nothing too complicated had to be argued.

PairTheBoard

[Capitan23]

arg, thinking too hard.

[michw]

Can we please get the answer in white so I can go to sleep?

[soon2bepro]

There's no solution to this. (unless there's some information you missed to provide)

There are only 4 possible settings for the two switches:
1) A up, B up
2) A up, B down
3) A down, B up
4) A down, B down

So there's no way for you to know just by getting in the room that 29 other people have been there, since there are only 4 possible settings and you'd need 29 at the very least (possibly more, since you have to take into account that whenever you get there you must move a switch even if you've been there before).

In your hint, nothing changes much, you have 2 possible settings with which you need to account for 29 other people. No way.

I guess the group strategy would be to wait a couple of months then say everyone has been there. Worth the risk.

[PairTheBoard]

Ok. I figured-remembered the trick. Once you see the trick you should be able to get it pretty easily.

Trick in White:
<font color="white"> The A switch is the Info-Switch and the B switch is the Noise Switch. If you want to do nothing you Flick the B switch.

Now, the Trick is you only let One Person Flick the A Switch Up. I think you would have to assign somebody that job. After he switches it Up, everybody else is only allowed to switch it Down. The Assigned Prisoner keeps count. He is the only one who Flicks the Switch more than once and he only Switches it back to the Up (Neutral) Position.
</font>

It's much easier to Figure-Remember than it is to Figure.

PairTheBoard