Prisoner dilemma

[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

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

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

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. [img]/images/graemlins/frown.gif[/img]