# Thirteen people telling truths or lies

• A: There are exactly 5 people telling truths, while others are telling lies.
• B: F tells lie.
• C: E tells lie.
• D: G tells lie.
• E: If D is telling truth, B is too.
• F: If E is telling lie, C is too.
• G: If H is telling truth, C is too.
• H: If M is telling truth, J is too.
• I: If I'm telling truth, A is telling lie.
• J: If you talk to L, you'll die today.
• K: If you talk to M, you'll die today.

If you talk to L or M, they will tell you whether K is telling truth (before you possibly die). Finally you solved the puzzle and deduced whether each person is telling truth, without dying in a few days. So who were telling truths?

Note:

There is an intended answer and a loophole answer sorry, two loophole answers. I didn't want to add too many words to close that loophole (turned out to be a bad idea).

Hint:

It's up to you to choose whether to talk with L, M, both or none in the story. And everything before the note except the final question is a premise that can be used.

• So we should assume that L and M always tell the truth about K? Jul 2, 2016 at 15:06
• @user314159 No. Jul 2, 2016 at 15:09
• Are they politicians? Jul 2, 2016 at 20:38
• @Richard If the "if I'm telling truth..." trick worked for politicians... Jul 3, 2016 at 19:46

We can write down the problem as a boolean formula.

We can treat the statement "person $X$ says $y$" as asserting "$X$ tells the truth and $y$ is true, or $X$ lies and $y$ is false." Abbreviating "$X$ tells the truth" as $X$, and the truth value of statement $y$ as just $y$, we have:

$$(X \land y)\lor(\neg X \land \neg y) \\ \equiv (X \Leftrightarrow y)$$

That is, whether or not $X$ tells the truth is logically equivalent to the truth value of their statement $y$.

Now we can write the whole puzzle as simply the conjunction of all the statements:

\begin{align} B &\Leftrightarrow \neg F \\ C &\Leftrightarrow \neg E \\ D &\Leftrightarrow \neg G \\ E &\Leftrightarrow (D \Rightarrow B) \\ F &\Leftrightarrow (\neg E \Rightarrow \neg C) \\ G &\Leftrightarrow (H \Rightarrow C) \\ H &\Leftrightarrow (M \Rightarrow J) \\ I &\Leftrightarrow (I \Rightarrow \neg A) \end{align}

For now I've skipped the first ($A$) and last two ($J$ and $K$) statements.

The equivalences mean that we can make some replacements:

\begin{align} B &\Leftrightarrow \neg F \\ C &\Leftrightarrow \neg E \\ D &\Leftrightarrow \neg G \\ E &\Leftrightarrow (\color{red}{\neg G} \Rightarrow \color{red}{\neg F}) \\ F &\Leftrightarrow (\neg E \Rightarrow \neg \color{red}{(\neg E)}) \\ G &\Leftrightarrow (H \Rightarrow \color{red}{\neg E}) \\ H &\Leftrightarrow (M \Rightarrow J) \\ I &\Leftrightarrow (I \Rightarrow \neg A) \end{align}

We can employ contraposition to eliminate the negations in $(\neg G \Rightarrow \neg F)\equiv(F\Rightarrow G)$. Then for $F$, we can write the implication in a logically equivalent form:

$$(\neg E \Rightarrow E) \equiv \neg\neg E \lor E \equiv E \lor E \equiv E$$

Therefore we have:

\begin{align} B &\Leftrightarrow \neg F \\ C &\Leftrightarrow \neg E \\ D &\Leftrightarrow \neg G \\ E &\Leftrightarrow \color{red}{(F \Rightarrow G)} \\ F &\Leftrightarrow \color{red}{E} \\ G &\Leftrightarrow (H \Rightarrow \neg E) \\ H &\Leftrightarrow (M \Rightarrow J) \\ I &\Leftrightarrow (I \Rightarrow \neg A) \end{align}

$E$ is a little trickier, since it is equivalent to an expression containing itself; we can try expanding the equivalence into the form from above:

$$E \Leftrightarrow (E \Rightarrow G)\\ \equiv (E \land (E \Rightarrow G))\lor(\neg E \land \neg(E \Rightarrow G)) \\ \equiv (E \land (\neg E \lor G))\lor(\neg E \land \neg(\neg E \lor G)) \\ \equiv (E \land \neg E) \lor (E \land G) \lor (\neg E \land E \land \neg G) \\ \equiv E \land G$$

Thus both $E$ and $G$ must be true (and by extension, $F$ is true as well):

\begin{align} B &\Leftrightarrow \color{red}{\bot} \\ C &\Leftrightarrow \color{red}{\bot} \\ D &\Leftrightarrow \color{red}{\bot} \\ E &\Leftrightarrow \color{red}{\top} \\ F &\Leftrightarrow \color{red}{\top} \\ G &\Leftrightarrow \color{red}{\top} \Leftrightarrow (H \Rightarrow \color{red}{\bot}) \\ H &\Leftrightarrow (M \Rightarrow J) \\ I &\Leftrightarrow (I \Rightarrow \neg A) \end{align}

Now $(H\Rightarrow\bot)\equiv \neg H$, so:

\begin{align} B &\Leftrightarrow \bot \\ C &\Leftrightarrow \bot \\ D &\Leftrightarrow \bot \\ E &\Leftrightarrow \top \\ F &\Leftrightarrow \top \\ G &\Leftrightarrow \top \\ H &\Leftrightarrow \bot \color{red}{\Leftrightarrow (M \Rightarrow J)} \\ I &\Leftrightarrow (I \Rightarrow \neg A) \end{align}

We can further assert $\neg(M \Rightarrow J) \equiv M \land \neg J$:

\begin{align} B &\Leftrightarrow \bot \\ C &\Leftrightarrow \bot \\ D &\Leftrightarrow \bot \\ E &\Leftrightarrow \top \\ F &\Leftrightarrow \top \\ G &\Leftrightarrow \top \\ H &\Leftrightarrow \bot \\ I &\Leftrightarrow (I \Rightarrow \neg A) \\ J &\Leftrightarrow \color{red}{\bot} \\ M &\Leftrightarrow \color{red}{\top} \end{align}

Finally, we can perform on $I$ the exact same expansion we did before on $E$:

$$I \Leftrightarrow (I \Rightarrow \neg A) \\ \equiv (I\land(I\Rightarrow \neg A))\lor(\neg I \land \neg(I\Rightarrow \neg A)) \\ \equiv (I\land(\neg I \lor \neg A))\lor(\neg I \land \neg(\neg I \lor \neg A)) \\ \equiv (I\land \neg I) \lor (I \land \neg A) \lor (\neg I \land I \land A)) \\ \equiv I \land \neg A$$

Thus, we now have:

\begin{align} A &\Leftrightarrow \color{red}{\bot} \\ B &\Leftrightarrow \bot \\ C &\Leftrightarrow \bot \\ D &\Leftrightarrow \bot \\ E &\Leftrightarrow \top \\ F &\Leftrightarrow \top \\ G &\Leftrightarrow \top \\ H &\Leftrightarrow \bot \\ I &\Leftrightarrow \color{red}{\top} \\ J &\Leftrightarrow \bot \\ M &\Leftrightarrow \top \end{align}

All that's left is to determine whether $K$ and $L$ tell the truth. We know that $A$ lies, thus there cannot be exactly five truth-tellers. But, since there are at least five truth-tellers ($E$, $F$, $G$, $I$, and $J$), at least one of $K$ and $L$ must tell the truth, leaving us with three possibilities (crosses are truth-tellers):

$$\begin{array}{ccccccccccccc}A&B&C&D&E&F&G&H&I&J&K&L&M\\\hline&&&&\times&\times&\times&&\times&&\times&\times&\times\\&&&&\times&\times&\times&&\times&&\times&&\times\\&&&&\times&\times&\times&&\times&&&\times&\times\\\end{array}$$

There are three pieces of information we haven't used yet:

• J: If you talk to L, you'll die today.
• K: If you talk to M, you'll die today.
• If you talk to L or M, they will tell you whether K is telling [the] truth.

I'll introduce a few more variables:

• $T_L$ and $T_M$ are true iff you talked to L or M, respectively.
• $K_L$ and $K_M$ are true iff L or M, respectively, would have claimed that K is a truth-teller.
• Finally $\mathit{Die}$ is true iff you died.

This lets us introduce four new formulae:

\begin{align} J &\Leftrightarrow (T_L \Rightarrow \mathit{Die}) \\ K &\Leftrightarrow (T_M \Rightarrow \mathit{Die}) \\ L &\Leftrightarrow (K \Leftrightarrow K_L) \\ M &\Leftrightarrow (K \Leftrightarrow K_M) \end{align}

We already know $M \Leftrightarrow \top$, allowing us to remove it:

\begin{align} J &\Leftrightarrow (T_L \Rightarrow \mathit{Die}) \\ K &\Leftrightarrow (T_M \Rightarrow \mathit{Die}) \\ K &\Leftrightarrow \color{red}{K_M} \\ L &\Leftrightarrow (K \Leftrightarrow K_L) \end{align}

We also know that $J \Leftrightarrow \bot$, allowing us to write:

$$\neg(T_L \Rightarrow \mathit{Die}) \\ \equiv \neg(\neg T_L \lor \mathit{Die}) \\ \equiv T_L \land \neg\mathit{Die}$$

Giving us:

\begin{align} T_L &\Leftrightarrow \color{red}{\top} \\ \mathit{Die} &\Leftrightarrow \color{red}{\bot} \\ K &\Leftrightarrow (T_M \Rightarrow \mathit{Die}) \\ K &\Leftrightarrow K_M \\ L &\Leftrightarrow (K \Leftrightarrow K_L) \\ \end{align}

This is somewhat uncomfortable; intuitively, negating the statement "if you talk to L, you'll die today" gives us no information about whether we will talk to L in the future! This is called a paradox of material implication. An interpretation of the statement "J says 'if you talk to L, you'll die today'" that is more in line with natural-language intuition might be:

$$J \Rightarrow (T_L \Rightarrow \mathit{Die})$$

That is, if J is a liar we gain no information from his statement.

Ignoring the paradox for now, we can simplify even further:

\begin{align} T_L &\Leftrightarrow \top \\ \mathit{Die} &\Leftrightarrow \bot \\ K &\Leftrightarrow K_M \Leftrightarrow \color{red}{\neg T_M} \\ L &\Leftrightarrow (K \Leftrightarrow K_L) \\ \end{align}

Now the table of possibilities looks like this (removing columns A–I):

$$\begin{array}{cccccccccccccccccc}J&K&L&M&T_L&T_M&K_L&K_M&\mathit{Die}\\\hline&\times&\times&\times&\times&&\times&\times&\\&\times&&\times&\times&&&\times&\\&&\times&\times&\times&\times&&&\end{array}$$

Now there is one more fact we were given:

you deduced whether each person is telling [the] truth

To use this we need to remember which columns of the table are directly observable. $T_L$ and $T_M$ are always observable. Depending on who you talk two, one or two more columns are also observable:

• If you talk to L only, $K_L$ is also observable, and the observable parts of the table looks like this:

$$\begin{array}{ccc}T_L&T_M&K_L\\\hline\times&&\times\\\times&&\end{array}$$

Note that only the rows in which $T_L\Leftrightarrow \top$ and $T_M\Leftrightarrow \bot$ were selected. Note that since the rows are different, we are able to distinguish between the two. This means that in either case, we would be able to uniquely determine who is lying and who is telling the truth.

• If you talk to both L and M, both $K_L$ and $K_M$ are observable and the table looks like:

$$\begin{array}{cccc}T_L&T_M&K_L&K_M\\\hline\times&\times&&\end{array}$$

There is only one row where both $T_L$ and $T_M$ are true, so there is only one row in the table: making this case uniquely identifiable as well.

If we instead use the intuitive formulation of J and K's statements, we would instead start off with:

\begin{align} J &\Rightarrow (T_L \Rightarrow \mathit{Die}) \\ K &\Rightarrow (T_M \Rightarrow \mathit{Die}) \\ K &\Leftrightarrow K_M \\ L &\Leftrightarrow (K \Leftrightarrow K_L) \end{align}

Now, substituting $J\Leftrightarrow \bot$ results in:

\begin{align} J &\Leftrightarrow \color{red}{\bot} \\ K &\Rightarrow (T_M \Rightarrow \mathit{Die}) \\ K &\Leftrightarrow K_M \\ L &\Leftrightarrow (K \Leftrightarrow K_L) \end{align}

Now our logic table has a full 20 possibilities!

$$\begin{array}{ccccccccc}J&K&L&M&T_L&T_M&K_L&K_M&\mathit{Die}\\\hline&&\times&\times&&&&&?\\&\times&&\times&&&&\times&?\\&\times&\times&\times&&&\times&\times&?\\&&\times&\times&&\times&&&?\\&\times&&\times&&\times&&\times&\times\\&\times&\times&\times&&\times&\times&\times&\times\\&&\times&\times&\times&&&&?\\&\times&&\times&\times&&&\times&?\\&\times&\times&\times&\times&&\times&\times&?\\&&\times&\times&\times&\times&&&?\\&\times&&\times&\times&\times&&\times&\times\\&\times&\times&\times&\times&\times&\times&\times&\times\end{array}$$

I've shortened the table a little by using a question mark where $\textit{Die}$ can be true or false. Once again we need to find which cases are uniquely identifiable.

• If you talk to neither L nor M, we are looking at the first three rows of the table. Only $T_L$ and $T_M$ are observable, so the three rows are not distinguishable. Therefore we can remove these three rows from the table.

• If you talk to M only, we look at the next three rows of the table. There is only one row with $K_M$ false, so that case is uniquely identifiable. However, the other two rows are not distinguishable, and get removed.

• If you talk to L only, we look at the next three rows of the table. There is only one row with $K_L$ true, so that case is uniquely identifiable. However, the other two rows are not distinguishable, and get removed.

• If you talk to both L and M, we look at the last three rows of the table. All of them are uniquely identifiable—but in the last two rows your death is guaranteed, which we know does not happen, and therefore those last two rows can be removed.

Combining both situations, we are left with five possible solutions to the problem, two in the formal interpretation and three in the intuitive interpretation (although only three are distinct in terms of who is telling the truth in each scenario):

$$\begin{array}{cccccccccccccccccc}A&B&C&D&E&F&G&H&I&J&K&L&M\\\hline&&&&\times&\times&\times&&\times&&\times&\times&\times\\&&&&\times&\times&\times&&\times&&\times&&\times\\&&&&\times&\times&\times&&\times&&&\times&\times\\\end{array}$$

• $(H\implies\bot)\equiv \not H$ should be $\neg(H\implies\bot)\equiv \not H$. For the final part, you have to use the fact stated in the last paragraph (before the note). Jul 2, 2016 at 19:18
• @user23013 My bad, that was supposed to be $(H \implies \bot)\equiv \neg H$ (I used \not instead of \neg by mistake). As for the last paragraph, I don't see how any of that information helps, since we don't know whether you talked to L or M (so we can't know if K was telling the truth), or what they would have said if you talked to them (so we can't know if L is telling the truth). Jul 2, 2016 at 19:22
• You can talk to both if you prefer. And everything except the final question is a premise. Jul 2, 2016 at 19:36
• @user23013 I think I know where the confusion is coming from. I assert that, even though we know J's statement ("If you talk to L, you'll die today") is false we cannot say that the opposite ("you talked to L and did not die today") is necessarily true, and that doing so would invoke the existential fallacy. Jul 2, 2016 at 20:02
• Yes, and that's what the "loophole answer" was referring to. But still, one of your 3 listed possibilities is impossible given those information. Jul 2, 2016 at 20:14

This might be the "loophole" answer you referred to:

A is lying. So more or less people may be lying.

So that means:

B:

Is telling the truth.

C:

Is lying.

D:

Is telling the truth.

E:

Is telling the truth.

F:

Is lying.

G:

Is lying.

H:

Is telling the truth.

I:

Is telling the truth.

J:

Is telling the truth.

K:

Is lying.

Which means:

You should talk to M, which will tell you that K is lying.

This might be a bit of a stretch, but it might just be your loophole. In the end, there were six people telling the truth. A lied.

• Incorrect. F: If E is telling lie, C is too. But in your answer, E is telling truth, so F can never be wrong. Jul 2, 2016 at 16:36

• That's not true @user23013. If F would be lying about a hypothetical, F does not say "E is lying, C is too" she says "If E is telling lie, C is too." As far as I am concerned $1,460$ of the $2^{13}=8,192$ possible scenarios are possible (I must dash now, but will check in later). Jul 2, 2016 at 17:44