Monday, February 13, 2017

The Sociologist (Some Unusual Knights and Knaves Part VIII)

On the next day, I met a sociologist who was visiting the island. He gave me the following report:

"I have interviewed all the natives of this island and I have observed a curious thing: For every native X, there is at least one native Y such that Y claims that X and Y are both knaves."

Does this report hold water?
(Source: To Mock a Mockingbird and Other Logic Puzzles: Including an Amazing Adventure in Combinatory Logic by Raymond Smullyan)

The report does not hold water.

If there is only one individual on the island, then X and Y must be the same person. A knight would not say X and Y are both knaves (i.e. he would not call himself a knave) and a knave would never say that any knave is in fact a knave.

If there are two or more individuals on the island, for any X, if X is a knave, there can be no other Y that would claim X and Y are both knaves. A knight would not claim they are both knaves, because that would be a lie. A knave cannot claim they are both knaves, because that would be the truth. If there at least two individuals on the island, and at least one is a knave, the report can't possibly hold water.

On the other hand, if there are two or more individuals on the island, for any X, if X is a knight, then there can be no other Y who would claim that both X and Y are knaves, for much the same reasons as before. If Y is a knight, then Y would obviously never say that X and Y are both knaves. And, while it is true that a knave Y would say of himself and a knight X that they are both knaves, reversing the values of X and Y would result in the predicament described in the previous paragraph.

Here is Smullyan's proof; it's shorter and I suspect it's essentially equivalent to mine but I don't fully understand it:
If the report is true, we get the following contradiction. For every X there is some Y who claims that X and Y are both knaves. Now, the only way that Y can claim that X and Y are both knaves is that Y is a knave and X is a knight. Therefore every inhabitant X of the island must be a knight. Yet for every inhabitant X there is at least one inhabitant Y who is a knave, since he claims that X and Y are both knaves. So there is at least one knave Y on the island. This contradicts the already proved fact that all the inhabitants are knights.

No comments:

Post a Comment