Day 339 – Logic Puzzle Answer

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.



Comments

Leave a Reply

Webmentions

If you've written a response on your own site, you can enter that post's URL to reply with a Webmention.

The only requirement for your mention to be recognized is a link to this post in your post's content. You can update or delete your post and then re-submit the URL in the form to update or remove your response from this page.

Learn more about Webmentions.