Who Is Telling the Truth?

Four possible islands

With two islanders, there are only four ways things could be. Asha is a truth-teller or a liar, and for each of those, Bikash is a truth-teller or a liar: 2 × 2 = 4 cases. A puzzle is solved when you know which case is the real one.

The rule for testing a case is always the same. Take each thing someone says. Work out whether it is true in that case. Then check it against the speaker:

A case survives only if every statement fits. Here is Asha’s “We are both liars” through all four cases:

Exactly one case is left standing, so it must be the real one. This is slow, but it can’t go wrong: nothing is missed, because every case is on the list.

When two people speak

Three islanders

On the other side of the island, three people are fishing: Asha, Bikash and Chandra (yes, the same names are popular there too). With three people each case is a choice for each of them: 2 × 2 × 2 = 8 cases.

Every statement is true or false

Puzzles like these are logic puzzles: no numbers to work out, only what follows from what. The whole island rests on one idea that mathematicians use all the time. A statement is a sentence that is either true or false, never both, never neither. “Bikash is a liar” is a statement. “Go away!” and “Is it raining?” are not.

And on this island, a person and their words are tied together: someone’s statement is true exactly when that someone is a truth-teller. Every puzzle is that one rule, applied to each speaker.

You have met something like this in Grade 7, in sets. Call the set of truth-tellers on the island T and the set of liars L. Every islander is a member of exactly one of them, so L is everything outside T. In the opening puzzle, T = {Bikash} and L = {Asha}. A case is just a choice of who goes into T: with two islanders there are 4 such choices, with three, 8, and each new islander doubles the number, because each old case splits into two. Ten islanders would mean 1,024 cases. That is why, past a few people, you need a cleverer way than writing them all down.

Two ways of proving

Look at what you did in the puzzles. Two methods came up, and both are among the most important tools in all of mathematics.

Proof by cases. List every possibility, rule out every one that fails, and see what is left. It is completely reliable, as long as the list really has every case. The tables above are proofs by cases. The tables of true and false that computer scientists use are called truth tables, and Grade 7 Computing builds them for AND, OR and NOT: Truth tables.

Proof by contradiction. Suppose something, follow where it leads, and if it leads to something impossible, your supposition was false. “If Asha were a truth-teller, she would be a liar” is a contradiction, so Asha is not a truth-teller. It sounds like a trick, but it is the usual way to prove that the primes never run out: see Is There a Biggest Prime Number?

What the opposite of a statement is

A liar’s words are false, so to use them you need the opposite of what was said. Opposites are trickier than they look.

• The opposite of “We are both liars” is not “we are both truth-tellers”. It is “at least one of us is a truth-teller”.
• The opposite of “At least one of us is a liar” is “neither of us is a liar”: both are truth-tellers.
• The opposite of “Everyone here is a liar” is “at least one person here is a truth-teller”, not “everyone here tells the truth”.

“Both” and “at least one” swap when you take the opposite. Augustus De Morgan, a British mathematician born in Madurai, India, in 1806, wrote rules for this, and they are named after him; Grade 7 Computing shows one as a truth table in Truth tables.

The useless question

Back at the tree, you would like to ask Asha a question instead of waiting for her to speak. The obvious one is: “Are you a truth-teller?”

But think about it. A truth-teller says Yes, truthfully. A liar says Yes, falsely. Every islander on the whole island gives the same answer, so that question tells you nothing at all.

A question whose answer you already know works much better. Ask, “Is 2 + 2 equal to 4?” A truth-teller says Yes, a liar says No, and the islander is unmasked by one word.

The fork in the road

Now a harder problem. You are walking to the island’s only village, and the path splits in two. One road goes to the village; the other goes into a forest. A guard stands at the fork, a truth-teller or a liar, you don’t know which. You may ask him one question that he can answer with Yes or No. What should you ask so that you can find the road, whatever he is?

“Does the left road go to the village?” fails: a Yes could come from a truth-teller with the village on the left, or from a liar with the village on the right. The question that works is a strange one:

“If I asked you ‘Does the left road go to the village?’, would you say yes?”

A truth-teller just answers truthfully: Yes if the village is on the left. Now follow the liar carefully when the village is on the left. Asked “Is it the left road?”, he would lie and say No. So the true answer to “would you say yes?” is No. But he lies about that too, and says Yes. The liar lies about his own lie, and the two lies cancel. When the village is on the right, the same happens the other way round: the truth-teller says No, and the liar, who would have lied “Yes”, lies about that and says No.

Figure 15.1 follows both guards. Whichever kind he is, Yes means left, and No means right. You don’t learn what the guard is, but you don’t need to: you learn the road.

This is a double negative: the opposite of the opposite is the original. Two minus signs make a plus, −(−5) = 5, for the same reason.

Words that tell you nothing

Not every puzzle has an answer. Try these, and count how many cases fit:

“I am a truth-teller” fits every case: a truth-teller says it truly and a liar says it falsely, just like the useless question. Asha could be either kind, and Bikash wasn’t even mentioned, so all four cases fit. “Bikash is a liar” fits two cases: either Asha tells the truth and Bikash lies, or Asha lies and Bikash tells the truth. You learn that they are different kinds, but not which is which.

A good logic puzzle is one where exactly one case fits. A maker of puzzles has to check that, by trying every case, just as you did.

Words nobody can say

Puzzle 3 is stranger: no case fits. If a truth-teller said “I am a liar”, it would be false; if a liar said it, it would be true. Nobody on the island can ever say it. So if you heard those words, you would know at once that the speaker was not one of our islanders at all: a visitor, perhaps, who lies only sometimes.

Off the island, the trouble gets worse. Take the sentence: “This sentence is false.” If it is true, then what it says holds, so it is false. If it is false, then what it says doesn’t hold, so it is true. This is the liar paradox, and it has puzzled thinkers for well over two thousand years. On the island, “I am a liar” simply can’t be said. But anyone can write “This sentence is false” on a piece of paper, and then the trouble is in the sentence itself. Thinkers have suggested many ways out; one is to say that such a sentence is neither true nor false, so it isn’t a statement at all. For more, see Can a Sentence Say It Is False? in Grades 9–12, below.

• Is a Pattern That Works Ten Times Always True? Why mathematicians want a proof, not just good examples, and how one counterexample settles it.
• Where Did the Missing Square Go? A picture that seems to prove something impossible, and the flaw hiding in it.
• Is There a Biggest Prime Number? Proof by contradiction at work: Euclid’s proof that the primes never end.
• Can a Sentence Say It Is False? (Grades 9–12) The liar paradox, and what it did to mathematics.
• How Is a Sudoku Solved in a Blink? (Computing, Going Further, Grades 9–12) Ruling out cases by the million.