Prisoner dilemma

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