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

[michw]

very nice

[PairTheBoard]

[ QUOTE ]
very nice

[/ QUOTE ]

Wish I'd thought of it the first time I saw the problem.

PairTheBoard

[soon2bepro]

Ah, dumb me. I never thought of the possibility of only one of the prisoners taking count. I thought either everyone or no one should know.

[borisp]

Bingo...another hint from the interview was "What if only YOU were allowed to make the announcement to the guards?" At that point my friend solved it. (I am terrible at this sort of quirky problem solving, which is probably why I find it fascinating.)

You mentioned monk/dots type problems...there is an interesting follow - up to this type of problem, probably more interesting than the problem itself. Here is the simplest version I know, maybe it's already been worked out here:

Suppose that on an island no one ever talks about eye color, looks in the mirror, etc. because of a strange custom: if you ever know your eye color for certain, you must take a pill that night that kills you in your sleep. Further, everyone has either blue or brown eyes, and they are perfectly rational, etc. Everyone knows the eye color of everyone but themselves. One day a traveler shows up and announces to the entire island "At least one of you has blue eyes."

An easy induction then shows that if N people have blue eyes, then on the (N+1)st day they don't wake up, and on the (N+2)nd day everyone else doesn't wake up. This proves that "If the traveler makes this announcement, then everyone dies."

However, is it an "only if?" Meaning, if 300 people live on the island, and 150 of them have blue eyes, the traveler is announcing information that everybody already knows. So why the need for the traveler? Why didn't everyone kill themselves already? What new info does he provide?

One common response is that the traveler provides the base case for the induction, which actually only demonstrates that he is needed for an inductive argument. Induction does not have a monopoly on proof techniques, so this isn't really a proof of necessity.

So the follow up question is to prove that "If the traveler never comes, then no one dies (from the custom)."

[Silent A]

[ QUOTE ]
Ah, dumb me. I never thought of the possibility of only one of the prisoners taking count. I thought either everyone or no one should know.

[/ QUOTE ]

Not dumb. The OP didn't clearly describe the problem (almost, but not quite).

[soon2bepro]

[ QUOTE ]
[ QUOTE ]
Ah, dumb me. I never thought of the possibility of only one of the prisoners taking count. I thought either everyone or no one should know.

[/ QUOTE ]

Not dumb. The OP didn't clearly describe the problem (almost, but not quite).

[/ QUOTE ]

Even if he didn't, from what he did say I believe I should've been able to draw the conclusion.

[soon2bepro]

[ QUOTE ]
So the follow up question is to prove that "If the traveler never comes, then no one dies (from the custom)."

[/ QUOTE ]

It's already been worked here:

http://forumserver.twoplustwo.com/showfl...rue#Post7711296 (http://forumserver.twoplustwo.com/showflat.php?Cat=0&amp;Board=scimathphil&amp;Number=771129 6&amp;Searchpage=1&amp;Main=7711296&amp;Words=%26quot%3Bsome+o f+you+have+horns%26quot%3B&amp;topic=&amp;Search=true#Post 7711296)

I don't know why you find this solution simple, to me it's very complicated. But I also don't understand why you are asking this once you have the solution. If you understand the induction then it becomes obvious that if the traveller doesn't come, the chain thinking event never gets started.

[borisp]

[ QUOTE ]
[ QUOTE ]
So the follow up question is to prove that "If the traveler never comes, then no one dies (from the custom)."

[/ QUOTE ]

It's already been worked here:

http://forumserver.twoplustwo.com/showfl...rue#Post7711296 (http://forumserver.twoplustwo.com/showflat.php?Cat=0&amp;Board=scimathphil&amp;Number=771129 6&amp;Searchpage=1&amp;Main=7711296&amp;Words=%26quot%3Bsome+o f+you+have+horns%26quot%3B&amp;topic=&amp;Search=true#Post 7711296)

I don't know why you find this solution simple, to me it's very complicated. But I also don't understand why you are asking this once you have the solution. If you understand the induction then it becomes obvious that if the traveller doesn't come, the chain thinking event never gets started.

[/ QUOTE ]
You quoted the last paragraph. The relevant portion to your "already solved" rebuttal is the second to last paragraph.

And when I say "simplest example" I don't mean simple in the absolute sense, I mean this is as easy as I can make this. But once one is told the content of the answer, and then asked to prove it by induction, the inductive argument is easy. When the problem is posed simply as "What happens??" then I agree it is very hard.

[PairTheBoard]

[ QUOTE ]
[ QUOTE ]
So the follow up question is to prove that "If the traveler never comes, then no one dies (from the custom)."

[/ QUOTE ]

It's already been worked here:

http://forumserver.twoplustwo.com/showfl...rue#Post7711296 (http://forumserver.twoplustwo.com/showflat.php?Cat=0&amp;Board=scimathphil&amp;Number=771129 6&amp;Searchpage=1&amp;Main=7711296&amp;Words=%26quot%3Bsome+o f+you+have+horns%26quot%3B&amp;topic=&amp;Search=true#Post 7711296)

I don't know why you find this solution simple, to me it's very complicated. But I also don't understand why you are asking this once you have the solution. If you understand the induction then it becomes obvious that if the traveller doesn't come, the chain thinking event never gets started.

[/ QUOTE ]


Here's a puzzle. Can you figure out the Phrase soon2bepro Searched on to bring up that Thread?

PairTheBoard

[Ringo]

[ QUOTE ]

An easy induction then shows that if N people have blue eyes, then on the (N+1)st day they don't wake up, and on the (N+2)nd day everyone else doesn't wake up. This proves that "If the traveler makes this announcement, then everyone dies."

[/ QUOTE ]

I don't get that. /images/graemlins/frown.gif

[borisp]

Induct on the number of people with blue eyes. If one person has blue eyes, that person takes the pill on the first night, since now they know they have blue eyes, since they only see people with brown eyes. On the second night, everyone else takes the pill, since the only person they have known on the island to have blue eyes has taken the pill. If any of those still living had had blue eyes, the lone person with blue eyes would not have done this. But he did do it, and now they know they all have brown eyes.

Now assume the statement "If there are N people on the island with blue eyes, then they wake up every day until the (N+1)st day, at which point they do not wake up, and everyone on the island knows this" is true. This is what we actually argue by induction.

(I admit here it is tricky because you have to slip in the auxiliary "everyone knows this" clause to complete the argument. But remember that we are just trying to prove that everyone dies, the actual statement we use for induction can be any true statement that will allow us to deduce this. The truth of this auxiliary statement in the base case follows from the rationality of the inhabitants.)

Suppose there are N+1 people on the island with blue eyes. On the (N+1)st day, they will all wake up. (Here we are tacitly assuming that the above statement is the only way they can deduce to kill themselves, which is really the content of the follow up question. I.e. in the absence of new information, everyone lives happily.) Each person with blue eyes only sees N people with blue eyes, so they deduce they must have blue eyes, since they know that it cannot be true that there are N people with blue eyes. (At this point, all of the blue eyed people know the above statement in the (N+1)st case, taking care of the "clause.") Now these N+1 people take the pill, don't wake up the (N+2)nd day, at which point the brown eyed people learn of the truth of the theorem in the (N+1)st case, they die, etc.

Sorry, I guess it's a bit arrogant to call this "easy" /images/graemlins/wink.gif

[borisp]

[ QUOTE ]
[ QUOTE ]
[ QUOTE ]
So the follow up question is to prove that "If the traveler never comes, then no one dies (from the custom)."

[/ QUOTE ]

It's already been worked here:

http://forumserver.twoplustwo.com/showfl...rue#Post7711296 (http://forumserver.twoplustwo.com/showflat.php?Cat=0&amp;Board=scimathphil&amp;Number=771129 6&amp;Searchpage=1&amp;Main=7711296&amp;Words=%26quot%3Bsome+o f+you+have+horns%26quot%3B&amp;topic=&amp;Search=true#Post 7711296)

I don't know why you find this solution simple, to me it's very complicated. But I also don't understand why you are asking this once you have the solution. If you understand the induction then it becomes obvious that if the traveller doesn't come, the chain thinking event never gets started.

[/ QUOTE ]


Here's a puzzle. Can you figure out the Phrase soon2bepro Searched on to bring up that Thread?

PairTheBoard

[/ QUOTE ]
"some of you have horns"? That's just from reading the URL on the link...

[PairTheBoard]

[ QUOTE ]
[ QUOTE ]
[ QUOTE ]
[ QUOTE ]
So the follow up question is to prove that "If the traveler never comes, then no one dies (from the custom)."

[/ QUOTE ]

It's already been worked here:

http://forumserver.twoplustwo.com/showfl...rue#Post7711296 (http://forumserver.twoplustwo.com/showflat.php?Cat=0&amp;Board=scimathphil&amp;Number=771129 6&amp;Searchpage=1&amp;Main=7711296&amp;Words=%26quot%3Bsome+o f+you+have+horns%26quot%3B&amp;topic=&amp;Search=true#Post 7711296)

I don't know why you find this solution simple, to me it's very complicated. But I also don't understand why you are asking this once you have the solution. If you understand the induction then it becomes obvious that if the traveller doesn't come, the chain thinking event never gets started.

[/ QUOTE ]


Here's a puzzle. Can you figure out the Phrase soon2bepro Searched on to bring up that Thread?

PairTheBoard

[/ QUOTE ]
"some of you have horns"? That's just from reading the URL on the link...

[/ QUOTE ]

I should have specified, "by looking at the Bolded words in the Thread".

PairTheBoard

[soon2bepro]

hehe, got me. That was what I remembered that would bring up only that thread /images/graemlins/smile.gif

It's been 8 months, what did you expect? =)

[soon2bepro]

I still don't understand why the people with brown eyes would die.

Once the last day has passed, and everyone with blue eyes dies, the brown eyed people know that none of them has blue eyes.

Btw, it's highly likely I could be making a mistake somewhere, because I find it extremely hard to think about this situation, even knowing the solution. I guess it's just because I want to go about it step by step.

[borisp]

This should have been more clearly stated in the assumptions: They all know that there are only two possibilities for eye color. So, when they have ruled out blue as a possibility, then they know they are all brown - eyed, which means they know their own eye color, which means it's suicide time.

Was this what was unclear? This might also shed light: when the brown eyed people see N+1 folks not wake up, they know that there were not N+2 people with blue eyes (i.e. that none of them have blue eyes) because if there were, then the N+1 blue eyed people would have had no way to draw the suicidal conclusion. I.e. they are all perfectly rational, and they all know that everyone else is perfectly rational, which is another necessary assumption that I should have made clearer.

[soon2bepro]

uh, I got confused because in the other thread DarrylP said something (probably a joke) about all the guys without horns becoming paranoid and leaving town also. Thought in this problem only the blue eyed people should die. My bad.

[MaxWeiss]

Actually I read the problem wrong. I thought there was only one switch. I stand by my statement if that were true. But I think misreading the original problem is far worse than sucking at doing the right problem, so I put on the dunce hat either way...

Edit: I just realized that what I responded to was in fact a one switch question. Ok, now I am puzzled. You say I am wrong and have a poor imagination, so now I'm curious <u>and</u> I feel bad! Please tell me the answer!!! I want to know how the one switch one would work!

[PairTheBoard]

[ QUOTE ]
Actually I read the problem wrong. I thought there was only one switch. I stand by my statement if that were true. But I think misreading the original problem is far worse than sucking at doing the right problem, so I put on the dunce hat either way...

Edit: I just realized that what I responded to was in fact a one switch question. Ok, now I am puzzled. You say I am wrong and have a poor imagination, so now I'm curious <u>and</u> I feel bad! Please tell me the answer!!! I want to know how the one switch one would work!

[/ QUOTE ]

In the One-Switch problem you have the option of doing nothing with the switch. In the Two-Switch problem you must Flick a Switch. So you Flick the B switch instead of doing nothing. The B-Switch just becomes a "Noise" switch then which carries no information. When the two switches are worked in that way it is equivalent to the One-Switch problem with the option of doing nothing.

PairTheBoard

[LeadbellyDan]

I not quite sure if this is right but I think if one of the islanders, Maud, one day announces:

"Some of you have blue eyes"

then everyone apart from Maud dies.

If Dave and Maud were they only islanders with blue eyes then Dave would immediately know his eye colour and kill himself on day 1.

If Maud has blue eyes and two other guys, Mark and Dave, also have blue eyes. Mark and Dave would wait to see if the other killed themself on day 1 and then if they didnt they would both realise they had blue eyes and would die on day 2. Meanwhile Maud is none the wiser of her own eye colour. The same thing would have happened if she had brown eyes.

On day 3 everyone else would realise they had brown eyes and would die. Maud would still be clueless.

Im pretty sure the induction works in the same way as the previous example for three or more blue eyes non-Maud islanders.

[borisp]

I wasn't necessarily accusing you of anything other than a common logical mistake, which usually goes something like "I can't imagine any way this is possible, therefore this is impossible." (Religious nuts love this line of reasoning.) I didn't really mean to come across as a jerk, but in retrospect it's pretty ridiculous for me not to expect otherwise. You don't necessarily have a poor imagination...but everyone's imagination fails, and it happens pretty often to everyone, especially those that choose to ponder these kinds of puzzles /images/graemlins/smile.gif

[David Steele]

I don't see how this works, the way the problem was described.
The guards could just go back and forth with the counter-guy and another guy and not have anyone else in for a long time.
The counter guy sets the other guy resets. How can the counter -guy tell when/if the other 28 have been in?

D.

[vhawk01]

They could go back and forth with a select few as long as they want, but those guys are just gonna be flipping the noise lever. This is going to take a LOT of iterations, because the only times the info lever is ever being flipped is either:

1) A guy comes into the room for his first time AND the lever is down
2) The counter comes into the room and the lever is up

In all other situations, only the noise lever is being flipped. If the guards are choosing at random, this is going to take probably thousands of iterations before he claims all have been through the room. Anyone wanna do the math real quick and figure out how many it should be?

[yteba]

Pretty boring switches. They just go up or down. Someone should die or something when you hit the switch, also WAY to long an explanation after which they problem is still pretty foggy. I say this version of the prisoners dilemma sucks.

[borisp]

[ QUOTE ]
Anyone wanna do the math real quick and figure out how many it should be?

[/ QUOTE ]
After about 3 minutes of thought, I think this would best be solved via numerical simulation on a computer. Without some nontrivial simplifying idea, it seems pretty intractible.

[vhawk01]

[ QUOTE ]
[ QUOTE ]
Anyone wanna do the math real quick and figure out how many it should be?

[/ QUOTE ]
After about 3 minutes of thought, I think this would best be solved via numerical simulation on a computer. Without some nontrivial simplifying idea, it seems pretty intractible.

[/ QUOTE ]

There is a reason I asked if anyone else wanted to do it and didn't work at it myself. /images/graemlins/grin.gif

[vhawk01]

[ QUOTE ]
Pretty boring switches. They just go up or down. Someone should die or something when you hit the switch, also WAY to long an explanation after which they problem is still pretty foggy. I say this version of the prisoners dilemma sucks.

[/ QUOTE ]

Its not a version of the prisoners dilemma.