Monday 2 April 2018

Answer to the Interstellar puzzle

In our Interstellar podcast, Thomas posed the following puzzle:

A group of people with assorted eye colors (say 10 blue and 10 brown) live on an island.

Everyone can see the eye colour of everyone else, but they can't communicate to each other to tell each other their eye colour.

Every night at midnight, a ferry stops at the island. Any islanders who have figured out the colour of their own eyes can leave the island.

One day a sailor from the ferry gets off the boat and says:

"I can see someone who has blue eyes".

Everyone hears and understand the statement, but the sailor is immediately shot dead for communicating with the islanders and no-one ever speaks again. However, given this information some people are able to figure out their eye colour.

Who leaves the island, and on what night?

The simple answer is that all 10 blue-eyed people leave on the tenth day. However, the thinking behind this answer is probably more important than the answer itself. Critically, this is a difficult puzzle. You need to have an extended chain of thinking, but, before we make a chain, let's start with a single link.

Let's make the puzzle as simple as possible. Suppose on the island there is only one person with blue eyes and a load of people with other colour eyes (it doesn't matter how many, or what colour, as long as they're not blue). This blue-eyed person would immediately realize that they had blue eyes because they could see no one else with blue eyes. Therefore, that person would leave on the first night.

Suppose, now, there are two people with blue eyes. They would both leave on the second night, because they would each look at the other blue-eyed person on the second morning and realize that the only reason the other blue-eyed person wouldn't leave on the first night is because they see another person with blue eyes. Seeing no one else with blue eyes, each of these two people realize it must be them.

Carrying on this argument inductively we see that n blue-eyed people would leave on night n because on the n-1 previous night they cannot deduce that the other blue-eyed people are not leaving because of them.

This is a slightly hand-wavy proof, but can be made more rigorous, indeed Reddit has a very formal proof.

One part that still blows our mind is that everyone can always see everyone else's eyes. So in the case of 10 blue-eyed people on the island everyone knows that there are blue-eyed people on the island, so what information have they gained from the sailor?

The answer is common knowledge, but we'll let Wikipedia explain that.

No comments:

Post a Comment

Who are we?

Contact Form


Email *

Message *