Fri 2 Nov 2007

## Blue Eyes: The “Hardest Logic Puzzle in the World” — not the solution

Posted by Happy under puzzle

Comments Off on Blue Eyes: The “Hardest Logic Puzzle in the World” — not the solution

There is a commonly given solution to this puzzle that depends on induction, but incorrectly in my view. Here’s why.

It is obvious that you can easily find solutions for the cases where the number of blue-eyed people is 1 or 2, and there is an obvious pattern to them.

The next step is to say “and therefore by induction” and give the solution for 100 blue-eyed people.

This step is false. It does not satisfy the necessary conditions for induction to take place.

Let me give an example in maths. You can define a factorial by an inductive process and use it as a rewriting rule.

Inductive:

Factorial N = N * factorial (N – 1)

Factorial 1 = 1

Rewriting:

Factorial 1 = 1

Factorial 2 = 2 * 1

Factorial 3 = 3 * 2 * 1

Factorial 4 = 4 * 3 * 2 * 1

Factorial 5 = 5 * 4 * 3 * 2 * 1

And so on

The solution as widely given cannot be used as a rewriting rule. That is, it is not possible to write out in full the solution for 3, and then 4 and then 5 blue-eyed people. The solution is incomplete, and attempting to use it in this way shows that this is so.

In a real solution it is indeed possible to write out the solution longhand for 5 blue-eyed people, without relying on induction. Having done so it will then become apparent how to rewrite it for 6, or 7 or for 100 people. This is the solution to seek.

Incidentally, this puzzle is a good illustration of the difference between first order knowledge, second order knowledge and so on. It does not depend on common knowledge.