A Blue-Eye Paradox: Solution Not Unique

[Ken G]

Well, the heart of a proof by induction is the proof that the case for n reduces to the case for n-1. That core is present in this problem. You're right, that if the number of islanders is given explicitly as 10, then it is not necessary to establish that for all n, the case for n reduces to the case for n-1, it's only necessary to establish it for n=1, n=2, n=3, ... n=10. But as far as the reasoning in this case, it's not any easier to establish it for the 10 instances than it is to establish it for the general case.

That's all true, all I'm saying is there is no need for any inductive axiom to solve a specific version of this puzzle. Yet the puzzle is still interesting. So the puzzle is not about the use of an inductive axiom, it's about the chain of logic you can produce by tracking what people know, and how they gain new information each day. So people who object to any proofs on the basis of how the induction is being done do not have a relevant objection to the puzzle solution. The discussion seemed in danger of getting off on a tangent about the use of inductive axioms, but what is interesting about the puzzle does not involve inductive axioms.

In other words, if you are using something that is true for N, and you are showing that if it is true for N, it is true for N+1, you are not invoking any additional information input to go from the N to the N+1 case. But in this puzzle, it is crucial that there is information input-- there is the new information that no one left on day N. That's what is crucial, and a proof for a given N can be supplied by explicitly enumerating all the possibilities, so induction is never necessary. Thus the puzzle isn't about induction, it is about how new information each day culls the possibilities when you think about what other people know. Induction is merely an elegant path to a solution, it's not a requirement so it cannot be the reason the puzzle works. If I generate the integers from 1 to 10 by adding 1 to each previous one, I may notice a certain self-similarity to what I am doing, but I am not doing induction because I have not invoked any inductive axioms.

An example would be, if I wanted to prove that all the integers from 1 to 10 are >0 and <11, I could simply enumerate the list, and the proof is done without induction. Or, I could say that if N>0, then N+1>0, and if N<11, then N-1<11, and prove it by noting that N=1 > 0 and N=10 < 11 and apply induction in both directions to show that all the numbers in the list are both > 0 and <11. The latter is shorter and more elegant, especially if the numbers get large, but the former proof is still a valid solution that is not inductive.

 

[andrewkirk]

Hi andrewkirk:

I think you are making the following point. The OP problem does not give a specific value for the number, say N, of blue-eyed people on the island. Therefore N is pronumeral, Therefore a induction proof is needed.

Is this correct?

Regards,
Buzz

Yes, that is correct.

I was unable to find your post on page 4 with "axiom 1". Did you mean (1) your post #204 on page 11?

The page reference is to page 4 of the linked proof, not page 4 of this thread.

 

[Buzz Bloom]

But there are not "analogous statements" being cited as such anywhere in the proof, there is simply A tracking the reasoning of B tracking the reasoning of C, etc. It's a simple chain of logic that can be explicitly enumerated.

Hi Ken:

I confess thinking about the complex chain of A knows that B knows, etc. gives me a headache.
@andrewkirk, in his post #271, agrees that an induction proof is needed to prove the result for the OP puzzle. From the above quote I get that you disagree with this for any specific case when N, the number of blue-eyed persons, is specified.

For the case when N=4, can you post just an informal outline of the steps in such a non-inductive proof? My intuition tells me that somewhere in the proof, even without induction, you will need to specifically prove something of the form:

IF N=1 THEN X.​

The alternative interpretation of "all persons on the island are completely logical" (which I mentioned in my post #266 that I would discuss in another post) will discuss the logical use of the above proposition in different plausible logic systems, leading to different results.

Regards,
Buzz

 

[Ken G]

For the case when N=4, can you post just an informal outline of the steps in such a non-inductive proof? My intuition tells me that somewhere in the proof, even without induction, you will need to specifically prove something of the form:

IF N=1 THEN X.​

If N=4, I will never need anything that says if N=1. Everyone in the tribe knows that N is either 3 or 4, so there is never an "if N=1", that would be an irrelevant hypothetical to all concerned. Here is an entirely non-inductive proof for N=4:

Let us say that the blue eyed people are named A, B, C, and D. Let us follow the logic of A. Prior to the visitor's statement, A knows that B knows that C knows there are blue-eyed people. However, A does not know that B knows that C knows that D knows there are blue-eyed people. After the visitor's statement, A does know that, and this is what makes all the difference. Since A now knows that B knows that C knows that D knows there are blue-eyed people, A will leave on day 4, and here is the proof of that.

It all starts with the key "IF":
IF A has brown eyes, then:
___B sees 2 blue eyed people, C and D. A knows that B will follow the following logic:
______B: IF I have brown eyes, then C only sees 1 person with blue eyes, and that is D. So B can conclude this will be C's logic:
___________C: IF I have brown eyes, then D will leave on day 1. But when day 1 comes and D does not leave, C concludes that he/she
___________has blue eyes also, which means that C and D will leave on day 2.
_______BUT that does not happen, so B knows that B has blue eyes also, and B, C, and D leave on day 3.
___BUT that does not happen, so the IF that started it all off must not be true.
THUS A has blue eyes.

Notice how the proof involves A thinking about what B is thinking about what C is thinking about what D is doing or not doing. We simply add the information that no one leaves on days 1, 2, or 3 wherever in that thinking that information is relevant, and we get the proof. There is no induction anywhere in this proof, there is only the nesting of one person thinking about another person thinking about another person.



​

 

[Buzz Bloom]

Hi Ken:

Thank you very much for your post. I now understand your logic, and I am impressed that the logic is completely clear without any need of inscrutable formal notation.

I think your demonstration is a clear example of what @stevendaryl said in his post #248.

I will need to take some time to think about the implications this has on my former thinking.

Regards,
Buzz

 

[maline]

and I am impressed that the logic is completely clear without any need of inscrutable formal notation.

The inscutable formal notation was introduced only to prove that the problem and its solution are in fact logically rigorous. It was never designed to be user friendly. There have been several fairly clear "natural language" presentations of the solution earlier in the thread.

 

[Buzz Bloom]

The inscutable formal notation was introduced only to prove that the problem and its solution are in fact logically rigorous.. . . . There have been several fairly clear "natural language" presentations of the solution earlier in the thread.

Hi maline:

My reference to the notation issue was to express my personal frustration regarding my own inadequacies.

I apologize for not noticing the other clear "natural language" proofs among the 275 posts of this thread. If you would post the post numbers for some of these, I would much appreciate it.

Regards,
Buzz