Saturday, May 10, 2014

Islanders with dotted forheads

Problem

There is an island with 100 women. 50 of the women have red dots on their foreheads, and the other 50 women have blue dots on their foreheads.
If a woman ever learns the color of the dot on her forehead, she must permanently leave the island in the middle of that night.
One day, an oracle appears and says "at least one woman has a blue dot on her forehead." The woman all know that the oracle speaks the truth.
All the woman are perfect logicians (and know that the others are perfect logicians too). What happens next?


Solution

Base case. Imagine the same situation, except with 1 blue dot and 99 red dots. The woman with the blue dot will see 99 red dots, and will realize the one blue dot must be her own. She will leave on the first night.
The next day, the other 99 women will see that the one woman they all knew had a blue dot is gone. This indicates to them that their own dot cannot be blue (since the woman wouldn't have left on the first night if she'd seen any blue dots). So they all know their dots are red. All 99 of them will leave on the second night.
Now for the inductive step.
Inductive hypothesis: If there are exactly N blue dots, every woman with a blue dot will leave on night N.

0 comments:

Post a Comment