Cracking The Coding Interview/Q 6.4

From Software Engineers Wiki
Jump to: navigation, search

A bunch of people are living on an island, when a visitor comes with a strange order: all blue-eyed people must leave the island as soon as possible. There will be a flight out at 8:00pm every evening. Each person can see everyone else's eye color, but they do not know their own (nor is anyone allowed to tell them). Additionally, they do not know how many people have blue eyes, although they do know that at least one person does. How many days will it take the blue-eyed people to leave?

Answer

There is at least one blue-eyed in the island. Let's say the number of blue-eyed is N.

  • Case N = 1

Blue-eyed person will see there is no other blue-eyed. There must be one blue-eyed person, and the person will leave on the first day.

  • Case N = 2

Blue-eyed people will see there is one blue-eyed. Other people will see there are two. They do not know exactly whether there are one or two. But from above case, they know that if N = 1, the blue eyed person will leave on the first day. On the day 2, they find that no one left the island, which proves that N != 1. Now they know N = 2, and whoever sees only one blue-eyed will leave on the second day.

  • Case N = 3

Blue-eyed people will see there are two blue-eyed. Other people will see there are thee. They do not know whether N = 2 or 3, but they know if N = 2, all blue-eyed will leave on the second day. On the third day, if there are still two blue-eyed, all blue-eyed will leave on the third day.

  • Case any N

This logic can expand to any N. On the Nth day, everyone who sees N-1 blue-eyed people will leave.

Reference

Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox