Previous posts have given the rules for the puzzle and explained why traditional solutions fall down. The following is a complete solution. I suggest you don’t look until you have tried to solve the puzzle for yourself.

The approach given here is to skip the usual cases for 1 or 2 blue-eyed people, and to write out in full the solution for 5 blue-eyed
people (and a sufficient quantity of non-blue-eyed people). It will become obvious how the solution can be rewritten for a larger (or smaller) number.
The solution starts *before* the Guru speaks, based on the the state of knowledge that can be deduced from the rules prior to that additional
information.

Step 1. We know there are exactly 5 blue-eyed people on the island, but none of
them know that. The blue-eyed people can see 4, so the range of possibilities
for them is “4 to 5”. The non-blue-eyed people can see 5, so the range of
possibilities for them is “5 to 6”.

I shall now name the 5 blue-eyed people Alice, Bob, Chris, Don and Elsie (or A
to E for short). Obviously A can see that B, C, D and E are blue-eyed. [We
don’t care about the non-blue-eyed people any longer.] Therefore:

Proposition 1 is that Alice thinks the minimum no of blue-eyed people is 4.
P1: A thinks minBEP = 4.

Step 2. A thinks about what B thinks. On the assumption that:
(a) A thinks A may not be blue-eyed, and
(b) A thinks B thinks B may not be blue-eyed,
(c) A thinks B may only see blue-eyed people C, D and E.

P2: A thinks B thinks minBEP = 3.

Step 3. A thinks about what B thinks C thinks. On the assumption that:
(a) A thinks A may not be blue-eyed, and
(b) A thinks B thinks B may not be blue-eyed,
(c) A thinks B thinks C thinks C may not be blue-eyed,
(d) A thinks B thinks C may only see blue-eyed people D and E.

P3: A thinks B thinks C thinks minBEP = 2.

[Can you see where this is heading?]

Step 4. This chain of “A thinks B thinks C thinks…” can be extended simply by
writing out Step 3 to whatever depth required. By doing that we have:

P4: A thinks B thinks C thinks D thinks minBEP = 1.
P5: A thinks B thinks C thinks D thinks E thinks minBEP = 0.

Step 5. Gotcha! Because A thinks B thinks C thinks D thinks E thinks there may
not be any blue-eyed people on the island, the announcement by the Guru changes
the status quo. Now A thinks B thinks C thinks D thinks E thinks minBEP = 1 and
therefore that E now thinks E is blue-eyed and therefore that E will leave the
island.

P6: A thinks B thinks C thinks D thinks E may leave on night 1. [He doesn’t.]

Step 6. While E not leaving is no surprise to A, A thinks B thinks C thinks D
thought E might have left on night 1, and (with this new information) that C
may now think that D thinks D has blue eyes. Therefore:

P7: A thinks B thinks C thinks D may leave on night 2. [He doesn’t.]

[Can you see where this is heading?]

Step 7. This chain of “A thinks B thinks C may leave…” can be shortened by
writing out Step 6 as required for each successive step. By doing that we have:

P8: A thinks B thinks C may leave on night 3. [He doesn’t.]
P9: A thinks B may leave on night 4. [He doesn’t.]

Step 8. Night 4 has passed with no departures and all the thought chains have
been proven false. As it happens, all 5 of the blue-eyed people have been using
exactly the same logic and they now all know that the minBEP = 5. Each of them
can see 4 others, so they know their own eye colour must be blue.

P10: A, B, C, D and E leave on night 5.

The key feature of this “proof” is the chain of “A thinks B thinks C thinks”,
and the way this chain is first constructed down to the point where minBEP=0
and then shortened, first by the Guru’s announcement and then by each passing
night. Once you accept this as valid, the proof stands as self-evidently
correct and can be extended from 5 blue-eyed people to any number.

Solution: 100 blue-eyed people leave on the 100th night. No-one else leaves.

_______________________________________________
IDS-General mailing list
IDS-General@lists.mensa.org.au
http://lists.mensa.org.au/mailman/listinfo/ids-general_lists.mensa.org.au