Truth-Tellers and Liars

Truth-tellers and liars problems (also called Knights and Knaves problems) are logic puzzles in which a set of statements is provided, but some of the statements are true and some of the statements are false. The goal of the puzzle is to determine which statements are true based on the information given.

Each truth-teller and liar puzzle lends itself to a variety of possible solutions, from casework to truth table considerations to contradiction shortcuts.

One approach to solving truth-tellers and liars problems is with systematic casework. Specifically, one can simply consider each possible "case," and see if this case is possible according to the given information. For example, consider this solution to the problem above using systematic casework.

There are 4 cases to consider depending upon who lied or spoke the truth:

Case 1: Both spoke the truth. Since one of them lied, this is not possible.

Case 2: Red shirt told the truth and Blue shirt lied. If only the person in the blue shirt lied, then he would be Bob, and the person in the red shirt would be Bob. Since neither of them are Andrew, this is not possible.

Case 3: Blue shirt spoke the truth and Red lied. If only the person in the red shirt lied, then he would be Andrew, and the person in the blue shirt would be Andrew. Since neither of them are Bob, this is not possible.

Case 4: Both of them lied. Hence the person in blue shirt is Bob and the person in red shirt is Andrew.

However, when using systematic casework, it's important to try to have as few cases as possible. For example, instead of working through the four cases of truths and lies, it might be simpler to consider the two cases of which person is which:

Case 1: Andrew is in the blue shirt and Bob is in the red shirt. Both of the statements would be true, which is not possible.

Case 2: Bob is in the blue shirt and Andrew is in the red shirt. Both of the statements would be false, which is possible. Thus, Andrew is wearing red.

Using systematic casework, try this problem:

The benefit of using clever casework is illustrated by the example below. Instead of considering $2^4 = 16$ possibilities for true and false statements, it suffices to simply consider the $4$ possibilities for which statement is false.

If exactly one of these statements is false, which statement is false?$$$$

A. Statement D is true.

B. Statement A is false.

C. Statement B is false.

D. Statement C is true.

---

Since one of the statements is false, it suffices to consider 4 cases, each case assuming one of statements to be false and then checking if this assumption is consistent with other statements or not.

Case 1: Statement A is false. This implies Statement D is false. Since no more than one statements can be false, this assumption is wrong.

Case 2: Statement B is false. This leads to conclusion that A is true, D is true, and C is true. (Looks good)

Case 3: Statement C is false. This results in conclusion of truthfulness of B, and thus fallacy of A, which is not possible.

Case 4: Statement D is false. It signifies that C is false, which is invalid.

So the statement which is wrong is Statement B. $_\square$

In the above example, all possible cases were enumerated and impossible cases were eliminated. However, in more difficult problems, it may be infeasible to work through every single case. Can you cleverly pare down the number of cases to check in the following problem?

Though it is always possible to do casework to determine the truth of each claim, it is not always optimal or practical to go through all of the cases one by one; there might be far too many cases to do this work by hand, and some of the cases may even be quite similar. It is always a good idea to keep our ideas as concise as possible while still conveying the logic clearly. If possible, it is recommended to find shortcuts and figure out how to shorten our solution. Three of these common shortcuts are

1. proving the right answer via contradiction;
2. conditioning on specific constraints;
3. identifying and eliminating contradictory statements.

Technique 1: Proving the correctness of our answer by contradiction.

A solution describing tedious casework is often neither engaging nor concise. Even worse, it is sometimes unnecessary. For instance, in the example below, the impossible cases "Rachel's statement is true" and "Samantha's statement is true" are subsumed by an argument assuming "Teresa's statement is false:"

Technique 2: Conditioning on specific constraints.

Rather than simply enumerating cases via the possible truth values, it is sometimes useful to enumerate cases by conditioning on another constraint given in the problem. One way to spot problems like these is to find terms like "at least," "at most," or "exactly" used in all the statements.

Consider the following example:

After Mrs. Jacobs' five children received their test scores, she asked them what their test scores were.

Her first child said that at least one of them failed algebra.
Her second child said that at least two of them failed algebra.
Her third child said that at least three of them failed algebra.
Her fourth child said that at least four of them failed algebra.

If only one child is telling the truth, can you determine how many of Mrs. Jacobs' children failed algebra?

---

It's possible to condition on truth values and check the five cases "child $x$ is telling the truth," but this isn't quite optimal. We would then have to keep track of two variables while working through cases, i.e. who's telling the truth, and how many children failed algebra. It is easier to just go ahead and condition on the number of children who failed algebra:

Suppose exactly 4 children failed algebra, then all of them are telling the truth, which contradicts our assumption.
Suppose exactly 3 children failed algebra, then her first three children are telling the truth, which contradicts our assumption.
Suppose exactly 2 children failed algebra, then her first two children are telling the truth, which contradicts our assumption.
Suppose exactly 1 child failed algebra, then only her first child is telling the truth, which satisfies our assumption.
Suppose none of the children failed algebra, then none of her children is telling the truth, which contradicts our assumption.

After exhausting through these 5 scenarios, we know that only the fourth scenario is possible, or simply put, her first child is telling the truth, and thus only one of her children failed algebra. $_\square$

Condition on specific constraints as you try solving these problems:

Technique 3: Identifying contradictory statements.

As mentioned above, it is not always ideal to solve problems like these by casework. But sometimes, it's easy to spot contradictory statements. For example:

Suppose there are 3 people A, B, and C, each of whom makes these claims:

Person A says, "B is telling the truth."
Person B says, "A is not guilty."
Person C says, "A is guilty."

Given that only one of them is telling the truth, can you determine who is guilty?

Trial and error would work here, but it isn't necessary. Notice that person B and person C gave contradicting viewpoints. So only one of them can be telling the truth, and the other must be lying. Because at least one of B and C is already telling the truth, A can't be telling the truth anymore. So A's statement is false, which means that B is not telling the truth. Thus C is telling the truth, or in other words, A is guilty.

The trick for these types of problems is to identify which pairs of statements can't be simultaneously true. Here's another problem where this technique applies:

Sometimes, a truth-tellers and liars problem can involve one or more self-referential statements. In other words, the statement makes a claim about its own truth or falseness. Here is a simple example to clarify this idea:

If the statement "this statement is both true and false" is logical, is the statement true or false?

---

A logical statement cannot be both true and false, so the statement must be false, which is consistent with the fact that it falsely claimed to be true (as well as false). $_\square$

The simplest way to evaluate a self-referential statement is to consider the cases where it is true or false, and then to consider if those would be logical (e.g., non-contradicting or otherwise absurd). In the previous problem, considering the case where the statement is true immediately shows this to be impossible (since the statement claims to be false). The following problem can be solved using this same idea of casework:

Sometimes, a statement cannot be made logically, and is simply impossible/logically inconsistent.

If the statement "this statement is false and it contains more than 5 words" is logical, is the statement true or false?

---

If the statement were true, then it would be false and contain more than 5 words. However, it cannot be both true and false! On the other hand, if the statement were false, then it would either have to not be false (impossible) or not contain more than 5 words (observably not the case), so it can't be false either. Thus, this statement is impossible/logically inconsistent. Don't make statements like these! $_\square$

When a problem statement allows us to pose a question to the truth-tellers and liars, we examine how much information is needed as well as how to obtain that amount of information in the allotted number of questions.

Common techniques to solve these problems include

• Eliminating a potential answer: "How can I ask a question such as if certain known conditions are met, the person cannot respond?"
• Truth tellers and liars function much like logic gates. Liars will "invert" the question, and truth tellers will allow the question to pass through. Because of this, we can look for questions that force certain responses. For example, a question going through a truth teller and a liar will come out as a lie, no matter who you ask first. Similarly, having a question go through a liar twice will invert their inversion, thus coming out as true.

Here are some examples of how we can apply these principles:

You approach two doors guarded by two gatekeepers. You know that one door leads to the exit, and the other leads into a never-ending maze, but you don't know which is which. You also know that one of the gatekeepers always tells the truth, and the other always lies, but you don't know which is which. You get one question to ask one of the gatekeepers to figure out which door leads to the exit. What do you ask?

---

In order to arrive at the correct answer, let's analyze the information given. We know that we can't tell which gatekeeper is which, so we need to think of a question that gives the same answer when a gatekeeper lies, and when a gatekeeper tells the truth.

One way to do this is to "link together" the truth-teller and the liar. Then, the question goes through both a truth teller and a liar, and you'll get the same answer no matter who you ask. To do this, we would need to ask one of the gatekeepers about the other.

If we ask one gatekeeper, "What would the other gatekeeper say is the door that leads to the exit?", the truth-teller, knowing that the other gatekeeper would say the bad door, would tell us the door that leads to the never-ending maze. The liar, knowing that the other gatekeeper would tell us the good door, would tell us the door that leads to the never-ending maze.

Since we have just found a question that gives the same answer no matter who we ask, we have just solved the problem, and should go through the opposite door of whatever the gatekeeper gives us. $_\square$

This problem is regarding a man who can never tell a lie. He says, "I have guessed a number from 1, 2, and 3. Can you, by asking me a single yes-no type question, find out the number I have chosen?" What would you ask?

---

Here observe that the possible options are three in number, i.e. 1, 2, and 3, while a yes-no question has two possible answers, i.e. "Yes," and "No." Since you need three pieces of information, the trick is to eliminate an option.

To do this, let's consider a case where the man cannot answer.

You can ask the following question: "From the number that you are thinking of, if you subtract 2 and take the square root of the result, will the answer be greater than 0?" See that if the man is thinking of 3, then $\sqrt { 3-2 } =1>0$ and his answer will thus be "Yes." In case the man is thinking of 2, $\sqrt { 2-2 } =0$ and his answer will be "No." However, if he is thinking of 1, then $\sqrt { 1-2 } =i$. Now the man can't say "No" in this case, since law of trichotomy says that if $a$ and $b$ are reals and $a$ is not greater than $b$ then $a$ has to be less than or equal to $b$, and here, $i$ being an imaginary number, has no defined order with respect to 0. Hence in this case the man will remain silent. $_\square$

You have been sent to a village to study the people residing there. Interestingly, there in the village reside two types of people: compulsive truth-tellers and compulsive liars. You are lost on a road which diverges into two: one leads to the village and the other to a jungle. You want to ask for directions as you want to go to the village. Luckily, you meet a man. But you don't know which class he belongs to: truth-teller or liar. If you're only allowed to ask one question that demands a yes-no answer, what should you ask?

---

You should ask a question that always gives you a positive answer. So you should ask a negation-of-negation type question like this: "If I show you this road and ask you whether it leads to the village, would you say yes?" The truth teller's case is trivial. In case the man is a liar and you have pointed the correct road and asked him whether it leads to the village or not, he would have said no. But since he has been asked whether he would have said yes and the true answer to this question is "No," he will tell you "Yes." Similarly in case of the wrong road, the liar will answer "No." $_\square$

Now try the following problems :

• Propositional Logic Word Problems
• SAT Logic
• Information Compression