Saturday, November 18, 2017

the island of knights and knaves

There is classic type of logic problem where we are asked to imagine an island consisting of two types of people: those that always tell the truth (knights), and those that always tell lies (knaves). In puzzles based on this trope, the islanders make statements, and we have to figure out which islanders are knights and which islanders are knaves.

This page will generate knight and knave puzzles of varying difficulty. Here’s an example:

An "easy" puzzle from https://dmackinnon1.github.io/knaves/

The grandfather of all these puzzles is an actual islander who referenced an actual island  - around 600 BCE, the Cretan Epimenides is credited with the statement “All Cretans are liars.” The fun has not stopped since.

The authoritative source for island puzzles is “What is the Name of this Book?” by Raymond M. Smullyan, which builds these seemingly simple puzzles from humble beginnings (knights and knaves alone on islands) to much more complicated ones that include normals (they sometimes lie, and sometimes tell the truth), the insane (they think lies are truths, and vice versa), monkeys, clubs of knights and knaves, vampires, werewolves and other characters. Using this motley crew, the book slyly leads us to a puzzle-based statement of Godel’s incompleteness theorem.

We will stick to the first type of puzzles: knights and knaves alone on an island. How do we solve the puzzle above? Here's one way to reason it out:

 
A sample solution for a puzzle generated
at https://dmackinnon1.github.io/knaves/

The puzzle generation page mentioned above limits itself to knights and knaves making three kinds of statements:

Accusations and Affirmations
In an accusation, an islander A says something like "B is a knave" or an equivalent statement like "B always lies." In an affirmation, islander A says something like "B is a knight" or "B always tells the truth."

Unfortunately, we don't know if A is telling the truth or not, so how can we know if what they are saying about B is true or not? Even without knowing the type of A, we can learn something very helpful about A and B from these statements. If A and B are linked by an accusation, they must be of different types: either A is a knave and B is a knight, or vice versa. If A and B are linked by an affirmation, they must be of the same type: either both are knights, or both are knaves. See if you can reason out why this must be so.

One approach to use when solving puzzles that feature several accusations and affirmations is to draw a diagram (as described in an old post).

Knave Conjunctions
An example of a knave conjunction, is when A says "B is a knight, or I am a knave," or  "C is a knave and I am a knave."

These are very helpful statements, as they always tell us the type of both the speaker and the spoken-of. Any islander who says "or I am a knave" will be making a statement that must be, overall, truthful and is therefore a knight, while any islander who says "and I am a knave" will by lying, and must be knave. Try and convince yourself of that.

An interesting thing about "knave conjunctions" is that their usefulness comes from how close they are to the liar paradox. The liar paradox is a more self-directed refinement of that original statement of Epimenides, where we imagine that someone says: "I am lying" and wonder if they are telling the truth or not.

An islander cannot make the statement "I am lying," or any equivalent statement such as "I am a knave." If such a statement is true, then the speaker is lying, making the statement also false; and if it is false, the speaker is lying, making the statement also true. So such a statement is contradictory - neither false or true, and our islanders are restricted to statements that are either true or false.

Islanders, however, can get close to generating the liar paradox by including its statement as a clause along with another statement. To see how they can do this, you have to be clear on how statements that include "and" and "or" work. If someone on the island says "X or Y" then only X or Y has to be true in order for the whole statement to be true. So a knight can say "X or Y" when only one of the statements is true. However, if a knave says "X or Y" then both X and Y must be false (if one was true, the whole statement would be true, and a knave cannot make a true statement). If an islander says "X and Y" then both X and Y have to be true in order for the statement to be true, and only one needs to be false for the statement to be false. So a knave can say "X and Y" when only one of the statements is false.

Similarity and Difference Statements
Sometimes an islander A might say "B is my type" or maybe "C is not my type." We might not know if A is a knight or knave, but we can infer the type of B and C right away. No matter whether A is lying or telling the truth, if A claims "B is my type," then B must be a knight. On the other hand, if A claims that "C is not my type" we know that C is a knave. Do you agree?

It is interesting to compare these statements with our first type of statements, the "accusations/affirmations," these two types of statements are reciprocal in a way. When an islander directly says what type another islander is (an accusation or affirmation), all we learn is that the source and target of the statement are similar or different, without learning the actual type. However, when an islander makes a statement about similarity or difference, we learn exactly what type the target is, without learning if this is similar or different than the source.

There are many more interesting things that islanders could say, but once you have reasoned out how these three kinds of statements work, you can beat any puzzle on the page.