On an island of knights, who always tell the truth, and knaves, who always lie, people stand in a queue. The person at the front says that everyone behind is a knave, and every other person says that the person directly in front is a knave. Is that enough to tell who is who? This page tries each possibility for the first speaker, shows that only one arrangement fits every statement, and finds that a queue of 25 holds exactly 12 knights and 13 knaves.
Key terms
Knights and knaves puzzle
Definition A knights and knaves puzzle takes place on an island where every inhabitant is either a knight, all of whose statements are true, or a knave, all of whose statements are false, and the task is to work out each speaker’s type from what they say. In the queue version, people stand one behind another, numbered 1 to from front to back. Person 1 says, “Everyone behind me is a knave.” Every later person , for from 2 to , says, “The person directly in front of me is a knave,” which means person . For every these statements allow exactly one assignment of types. The people in odd positions are knaves and the people in even positions are knights, so the queue has knights when is even and knights when is odd. For there are 12 knights, in positions 2, 4 and so on up to 24, and 13 knaves, in positions 1, 3 and so on up to 25. With only two people the answer is no longer unique, since both knight then knave and knave then knight fit the two statements. The name comes from the logician Raymond Smullyan, who made puzzles of this kind popular, for example in his 1978 book What Is the Name of This Book?
In plain words Every statement after the first accuses the person in front. A knight’s accusation must be correct and a knave’s must be wrong, so each person’s type is decided by the type of the person in front, and the first statement decides how the chain begins.
Example Take five people, and suppose first that person 1 is a knight. Then the statement is true, and persons 2 to 5 are all knaves. Person 2’s statement, that person 1 is a knave, is false, which suits a knave. But person 3’s statement, that person 2 is a knave, is true, and a knave cannot say something true. So person 1 is a knave, and the claim “Everyone behind me is a knave” is false, which means that at least one person behind person 1 is a knight. Now person 2 truthfully calls person 1 a knave, so person 2 is a knight. Person 3 falsely calls person 2 a knave, so person 3 is a knave, and in the same way person 4 is a knight and person 5 a knave. Checking every statement confirms this assignment. Person 1’s claim is false because persons 2 and 4 are knights, persons 2 and 4 correctly call the knave in front of them a knave, and persons 3 and 5 wrongly call a knight a knave. The queue has 2 knights and 3 knaves.
Truth-tellers and liars
Definition In logic puzzles a truth-teller is a speaker all of whose statements are true, and a liar is a speaker all of whose statements are false. A statement is judged as a whole. When a liar speaks, what is actually true is the negation of the statement, the statement that says exactly the opposite. The negation of “everyone in a group has a property” is “at least one member of the group does not have it”, and the negation of “A and B are both knaves” is “at least one of A and B is a knight”. So a false statement about several people does not mean that each of its parts is false.
In plain words A liar’s sentence only has to be wrong somewhere. A false claim that everyone behind is a knave needs just one knight behind to make it false.
Example Person A says, “We are both knaves,” about A and another person B. If A were a knight, the statement would be true, and A would be a knave, which is impossible. So A is a knave, and the statement is false, which means that at least one of the two is a knight. Since A is a knave, B is a knight. Reading the false statement as “we are both knights” would turn each part around, and it would make A a knight, which was already ruled out. Some statements carry no information at all. Anyone can say “I am a knight”, a knight truthfully and a knave falsely. Nobody on the island can say “I am a knave”, since from a knight it would be false and from a knave it would be true.
Logical consistency
Definition A collection of requirements is logically consistent when there is at least one way to satisfy all of them at once. In a knights and knaves puzzle, an assignment of types to all the speakers is consistent when, for every speaker, the speaker is a knight exactly when that speaker’s statement is true under the assignment. The truth of each statement is judged under the full assignment, including the types of the people it mentions, so changing one person’s type can affect several statements. The solutions of the puzzle are exactly its consistent assignments, and a puzzle may have none, exactly one or several.
In plain words A proposed answer is consistent when every speaker’s words fit the type you gave them, with no exceptions. Checking a pattern against every statement is what turns a likely answer into a proven one.
Example In a queue of two, person 1 says that everyone behind is a knave, which here means only person 2, and person 2 says that person 1 is a knave. The assignment knight, knave is consistent, since person 1 then speaks truly and person 2 falsely. The assignment knave, knight is consistent too, since person 1’s claim about person 2 is then false and person 2’s claim about person 1 is true. The other two assignments fail. With knight, knight, person 1 would be a knight making a false claim, and with knave, knave, person 1 would be a knave making a true one. So this puzzle has two solutions, and the step that rules out a knight at the front of a longer queue needs a third person.
Case analysis
Definition Case analysis is a method of proof that splits a problem into cases that together cover every possibility, works out the consequences in each case, and discards every case that leads to a contradiction. A contradiction shows that a case is impossible, and whatever holds in every remaining case is proved. A case that survives its first few checks has not yet been shown to work, so each surviving case must be checked against every condition at the end. In a knights and knaves puzzle the natural cases are the two possible types of one well-chosen speaker.
In plain words When you do not know which way something goes, try each way in turn and follow it until it breaks or until every condition has been checked. If only one way survives, it must be the truth, provided the cases covered everything.
Example For the queue of 25, split on person 1, who is either a knight or a knave. If person 1 is a knight, then persons 2 to 25 are knaves, and person 3, a knave, makes the true statement that person 2 is a knave, a contradiction. So person 1 is a knave. From there each type is forced one step at a time. If person is a knave, person ‘s accusation is true and person is a knight, and if person is a knight, the accusation is false and person is a knave. Hence the types alternate, with knaves at the 13 odd positions from 1 to 25 and knights at the 12 even positions from 2 to 24. A final check completes the proof. Person 1’s claim is false because person 2 is a knight, and every later statement fits its speaker.
Check yourself
- Change the number. A queue of 10 people makes the same statements as in the main puzzle. How many knights are there, and where do they stand?
Show the answer
The argument about person 1 only uses persons 1 to 3, so it works again. If person 1 were a knight, persons 2 to 10 would be knaves, and person 3 would be a knave making the true statement that person 2 is a knave, which is impossible. So person 1 is a knave, and the types alternate from there. Knights stand at the even positions 2, 4, 6, 8 and 10, and knaves at the odd positions 1, 3, 5, 7 and 9, so there are 5 of each. Person 1’s statement is false because person 2, for example, is a knight. Each knight correctly calls the knave in front a knave, and each knave from person 3 on wrongly calls the knight in front a knave.
- Change the first statement. In a queue of five, person 1 now says, “At least one person behind me is a knave,” and everyone else again calls the person in front a knave. Find all consistent assignments.
Show the answer
The later statements still force the types to alternate, so the whole queue is decided by person 1.
Suppose person 1 is a knight. The types are knight, knave, knight, knave, knight, and person 1’s statement is true because persons 2 and 4 are knaves. Every later statement also fits, so this assignment is consistent.
Suppose instead that person 1 is a knave. The types are knave, knight, knave, knight, knave. For person 1’s statement to be false, everyone behind person 1 would have to be a knight, but persons 3 and 5 are knaves. So the statement is true, and a knave cannot say it.
The only solution is knight, knave, knight, knave, knight, with 3 knights and 2 knaves. Changing “everyone” to “at least one” reverses every type in the answer.
- Find a puzzle with no answer. In a queue of two, person 1 says, “The person behind me is a knight,” and person 2 says, “The person in front of me is a knave.” Find all consistent assignments. Then take a queue of 25 in which person 1 says, “Everyone behind me is a knight,” and everyone else speaks as in the main puzzle.
Show the answer
For two people, test all four assignments. With knight, knight, person 2 is a knight whose claim that person 1 is a knave is false. With knight, knave, person 1 is a knight whose claim that person 2 is a knight is false. With knave, knight, person 1 is a knave whose claim that person 2 is a knight is true. With knave, knave, person 2 is a knave whose claim that person 1 is a knave is true. Every assignment fails, so no consistent assignment exists, and this conversation cannot happen on the island.
For 25 people, suppose person 1 is a knight. Then person 2 is a knight too, and person 2’s claim that person 1 is a knave is false, a contradiction. So person 1 is a knave, and the types alternate, knave, knight, knave and so on. Person 1’s claim is then false because person 3 is a knave, as a knave’s claim must be. The answer is the same as in the main puzzle, 12 knights and 13 knaves. With this first statement, every queue of three or more people has exactly one solution, while the queue of two has none.