Day 339 – Logic Puzzle Answer

December 5, 2009

Here is the answer to the Blue Eyes Logic Puzzle I posted.

This answer comes from mathematician Terence Tao, and has to do with common knowledge.

100 days after the Guru’s comment, all the blue eyed people will leave. This is proven as a special case of

Proposition. Suppose that the tribe had n blue-eyed people for some positive integer n. Then n days after the traveller’s address, all n blue-eyed people leave the island.

Proof: We induct on n. When n=1, the single blue-eyed person realizes that the traveler is referring to him or her, and thus leaves on the next day. Now suppose inductively that n is larger than 1. Each blue-eyed person will reason as follows: “If I am not blue-eyed, then there will only be n-1 blue-eyed people on this island, and so they will all leave n-1 days after the traveler’s address”. But when n-1 days pass, none of the blue-eyed people do so (because at that stage they have no evidence that they themselves are blue-eyed). After nobody leaves on the (n-1)st day, each of the blue eyed people then realizes that they themselves must have blue eyes, and will then leave on the nth day.

If you need any explanation of this, let me know.