4 ms·
The key of the problem includes the statement that all the islanders have seen all the other islanders and know their eye colors. From there we have the simple
by ubernostrum 11y ago
The key of the problem includes the statement that all the islanders have seen all the other islanders and know their eye colors.
From there we have the simple case of n = 1: suppose Bob is the only blue-eyed islander. He's seen everyone else's eyes, knows nobody else has blue eyes, and so can conclude from n >= 1 that in fact n = 1 and he is that one.
For the case of n = 2: suppose Alice and Bob are the two blue-eyed islanders. Alice knows Bob is blue-eyed but doesn't know she is. Bob knows Alice is blue-eyed but doesn't know he is. There are two possibilities: n = 1 or n = 2, since they have seen every other person's eyes and know there are no other blue-eyed people. Each can watch the other's behavior on the first day. But since neither one knows their own eye color yet, neither one commits suicide that day. Then each one realizes that for the other not to commit suicide, it must be the case that n > 1. Since they know every other person's eye color, the only possible explanation is "n = 2 and I'm the other one". They commit suicide on day 2.
From there we can just apply the same reasoning every time. If n = 3, Alice, Bob and Carol each look for the other two to commit suicide on the second day (from the reasoning for n = 2). When they don't, the only possible conclusion is "n = 3 and I'm the third one" and they all commit suicide on day 3.
That line of reasoning then works with any successive value for n: if there are n blue-eyed islanders, each looks for the other n - 1 islanders to commit suicide on day n - 1. When that doesn't occur, the only possible conclusion those people can reach is "there's one more blue-eyed islander, and it's me". Then all n of them commit suicide on day n.
- ars 11y agoThanks, that helps a lot. But the flaw is assuming that they will start counting at one. The blue eyed person number 3 can see that there are 2 others at least, so they know for sure that n != 1, since n != 1 they have no reason to expect anyone to commit suicide. So the whole sequence never gets started.
- anonymoushn 11y agoEdit: I wrote a comment here but this comment by aetherson is better https://news.ycombinator.com/item?id=10821119 https://news.ycombinator.com/item?id=10821119
- ubernostrum 11y agoThe sequence gets started by the initial statement, and although in the case of n > 1 it seems as if it doesn't impart any new information, it does. The distinction that matters to get the chain started is the difference between "I personally know there is at least one blue-eyed islander" and "everybody knows there is at least one blue-eyed islander and I know everybody knows it and they know I know it and I know they know I know it... (so on)". Prior to that you can't know that other islanders could deduce all the things you can deduce from available information, and they can't know that you could deduce all the things they could. Afterward, you know exactly what they can deduce from the available information, they know what you can deduce, and you know that it produces a guaranteed conclusion, by day n, that n is the number of blue-eyed islanders.