Logic puzzle - problem 298, linked below

Question

http://www.jstor.org/discover/10.4169/mathhorizons.21.2.30?uid=3739576&uid=2&uid=4&uid=3739256&sid=21103171332151

Paraphrased (not by OP) the problem from the above link is:

Three identical triplets (#1, #2, #3) sit in front of Derek. Exactly one is the thief. Exactly one is called Doctor, and the others always lie. "#1, is #2 the thief?" "Yes." "#2, is #1 the thief?" "Yes." "#3, [some question]" "[either yes or no]" Now Derek knows who is the thief. Who is it, and what were the last question and answer?

I'm wondering if this puzzle is truly solvable. If we assume that person #3 is lying and answers "yes" to the question "Did person #1 lie?" then we can figure out that it was person #2 (because if he answers "yes, person #1 lied," that means that person #1 was not lying when he claimed that #2 stole the manuscript). But we don't know if person #3 was lying or not...can anyone figure out how to prove this?

Answer 1

One solution is to see that if we can know that Doctor is in seat 3, we will know that the first two lied and the thief is in seat 3. One question and answer that will work is "Are you Doctor? No." Neither of the two others can answer that question negatively. It would be nice to find a question that forces Doctor to identify himself if he is in seat 3, but as I read the question that is not required.

Added: I haven't found any others, but have not proven that there are not some. If seat 3 tells a routine lie, we can't know anything. If seat 3 tells a routine truth, the same argument applies, so it could be "What is $2+2?\ \ 4$" as well. It would be useful to know what restrictions there are on Doctor. Can he make any statement, or must he decide whether to lie or tell the truth consistently, even if he makes a compound statement? Then we should be able to construct some statements that convince us that 1 or 2 is Doctor and telling the truth. I don't have one.

Answer 2

The problem (our information) is completely symmetric in $1$ and $2$. If one of them would have been the thief, it could have just as well been the other one. Thus, in that case, we cannot conclude who did it. So person $3$ must have stolen the paper. Now, we only need to know which question to ask...

EDIT
Oops, this won't work, because your question can make the information asymmetric.

Answer 3

Let $L_x$ be that the person seated in position $x$ is a liar.

Let $T_x$ be that the person seated in position $x$ is the thief.

There are 6 Boolean variables to variables to consider, so initially 64 satisfying cases. The we are given information in terms of who said what about who, leaving only the following 5 possibilities (using blank space for false):

$$\begin{array} {c|c c c |c c c|} \hline & L_1 & L_2 & L_3 & T_1 & T_2 & T_3 \\ \hline \text{Row 1} & T & & T & T & & \\ \hline \text{Row 2} & & T & T & & T & \\ \hline \text{Row 3a} & T & T & & & & T \\ \text{Row 3b} & & T & T & & & T \\ \text{Row 3c} & T & & T & & & T \\ \hline \end{array}$$

Now we put to the third chair some function $F(L, T)$. If he answers "yes", we only keep rows with the property $L_3 \rightarrow \lnot F(L, T)$. If he answers "no", then we only keep rows with the property $L_3 \rightarrow F(L, T)$.

Let $P$ be the set of rows for which $F(L, T)$ is true.

Let $Q$ be the set of rows for which $F(L, T)$ is false.

Let $R$ be the set of rows for which $L_3$ is true.

If seat 3 answers "yes", we eliminate rows $P \cap R$. If seat 3 answers "no", we eliminate possibilities $Q \cap R$. Note that we can never eliminate Row 3a. So regardless of what we choose for the question and what the response is, Row 3a will always remain a possibility.

In Row 3a, seat 3 is the thief. So, assuming only a yes/no question was asked, if the interviewer knows who the thief is after one question then it must be the occupant of seat 3, and rows 1 and 2 must have been eliminated.

One possible question-response would be $F(L, T) = T_1 \lor T_2$, in English, "Is the thief in seat 1 or seat 2", answer "yes".

The questions that can answer this are exactly those for which $F$ is chosen so that $ \{\text{Row 1}, \text{Row 2}\} \subseteq P$ with response "yes" or $ \{\text{Row 1}, \text{Row 2}\} \subseteq Q$ with response "no".

Answer 4

My solution is somewhat along the lines of Ross's. I believe the crucial part of the question is that whatever #3 says, it confirms Derek's belief in his identity.

Triplet #3 can either be the Doctor or not. If he is the Doctor, then he must also be the thief, as 1 and 2 are both liars. If he does not reveal himself to be the doctor, then we're exactly where we started, so we can give no solution.

Not all hope is lost. We can construct a question that would be unanswerable if #3 is not the Doctor. Such a question might be "If I were to ask 1 and 2 if they were the doctor, will one of them answer no?"

If #3 is a liar and therefore not the Doctor, it would be impossible for him to evaluate the question, and therefore impossible for him to lie. Only the Doctor is capable of answering the question, and so reveals himself.

If we're not permitted to use unanswerable questions, we can simply ask "Is one of you the Doctor?" If #3 answers "yes," we know he must be the doctor, as he is the only one capable of doing so.

Answer 5

In this answer we will construct a solution using propositional logic.

First, let's see how to formalize this problem. We call the three distinct persons $\;B1,B2,B3\;$ (for Berkove), exactly one of them is $\;Th\;$ (the thief), and exactly one of them is $\;Do\;$ (Doctor). For any person $\;x\;$, we have $$ (0) \;\;\; x\text{ says }p \;\Rightarrow\; (x \ne Do \;\Rightarrow\; \lnot p) $$ in other words, every non-Doctor is a consistent liar.

Applying $(0)$ three times, Derek knows that \begin{align} (1) \;\;\; & B1 \ne Do \;\Rightarrow\; B2 \ne Th \\ (2) \;\;\; & B2 \ne Do \;\Rightarrow\; B1 \ne Th \\ (3) \;\;\; & B3 \ne Do \;\Rightarrow\; (q \not\equiv a) \\ \end{align} where $\;q\;$ is a boolean expression representing the last question, and $\;a\;$ is either $\;\text{true}\;$ for "yes" or $\;\text{false}\;$ for "no".

And from these, it is possible for Derek to deduce who is the thief. So formally, we are asked to find some $\;x,q,a\;$ for which $$ (4) \;\;\; (1) \land (2) \land (3) \;\Rightarrow\; x = Th $$

---

Now to a solution. From $(1)$ and $(2)$ and the distinctness of the persons it is clear that \begin{align} & B3 = Do \\ \equiv & \;\;\;\;\;\text{"$\;B1,B2,B3\;$ are distinct"} \\ & B1 \ne Do \;\land\; B2 \ne Do \\ \Rightarrow & \;\;\;\;\;\text{"(1); (2)"} \\ & B2 \ne Th \;\land\; B1 \ne Th \\ \equiv & \;\;\;\;\;\text{"$\;B1,B2,B3\;$ are distinct"} \\ & B3 = Th \\ \end{align} or in other words $$ (5) \;\;\; B3 = Do \;\Rightarrow\; B3 = Th \\ $$

Using this to rewrite our goal $(4)$, we are given $(1)$ and $(2)$, and therefore $(5)$, and we are asked to solve $$ (4') \;\;\; B3 = Do \;\lor\; (q \not\equiv a) \;\Rightarrow\; x = Th $$

for $\;x,q,a\;$. We calculate \begin{align} & B3 = Do \;\lor\; (q \not\equiv a) \;\Rightarrow\; x = Th \;\;\;\;\;\text{-- $(4')$} \\ \equiv & \;\;\;\;\;\text{"logic: split $\;\Rightarrow\;$ on antecedent"} \\ & (B3 = Do \;\Rightarrow\; x = Th) \;\land\; ((q \not\equiv a) \;\Rightarrow\; x = Th) \\ \equiv & \;\;\;\;\;\text{"choose $\;x = B3\;$ -- strongly suggested by $(5)$"} \\ & (B3 = Do \;\Rightarrow\; B3 = Th) \;\land\; ((q \not\equiv a) \;\Rightarrow\; x = Th) \\ \equiv & \;\;\;\;\;\text{"logic: use (5) and simplify; rewrite $\;p \Rightarrow q\;$ as $\;\lnot p \lor q\;$"} \\ & (q \equiv a) \;\lor\; B3 = Th \\ \equiv & \;\;\;\;\;\text{"choose $\;q \;\equiv\; B3 = Th\;$ and $\;a \equiv \text{false}\;$} \\ & \;\;\;\;\;\phantom"\text{-- it seems simplest to go for the excluded middle"} \\ & (B3 = Th \;\equiv\; \text{false}) \;\lor\; B3 = Th \\ \equiv & \;\;\;\;\;\text{"logic: rewrite $\;p \equiv \text{false}\;$ as $\;\lnot p\;$; excluded middle"} \\ & \text{true} \\ \end{align}

Therefore we have found $\;x,q,a\;$ which satisfy $(4')$ and therefore $(4)$. This solution is that #3 ($\;B3\;$) is the thief; the question ($\;B3 = Th\;$) is, "Are you the thief?"; and the answer ($\;\text{false}\;$) is, "No."

Update. Another answer to this question pointed me to an even simpler solution, one where both $\;q\;$ and $\;a\;$ are $\;\text{true}\;$: Derek asked, "Does 1+1=2?" with the answer, "Yes." Or make both $\;\text{false}\;$: "2+2=5?" "No."

Answer 6

If one can deduce from #3's answer that #1 is the thief or that #2 is the thief then one has also deduced that #3 is not the doctor. However this is impossible as the doctor may lie or tell the truth, so no answer is inconsistent with #3 being the doctor. Therefore #3 is the only possible thief.

[Q: "Does 1+1=2?", A: "Yes"] => #3 is the doctor and hence the thief.

A couple of points:

Note this assumes that Derek does not know for certain that the doctor would not say yes or no if he does not know the answer. As you are not told that Derek has any such information it is reasonable to assume this, or even the stronger statement that the doctor would actually answer yes or no to a question he did not know the answer to, or the even stronger statement that the doctor is omniscient, hence able to lie or tell the truth at will.

Paradoxical answers are false (eg. 'are you lying?', 'yes') as being true leads to a contradiction. Questions may have 'yes' and 'no' both right (eg. "are you about to say "yes"?") or both wrong (eg. "are you about to say "no"?"). None of these raises any issues with the argument given above, as in all cases the doctor is still free to say 'yes' or 'no'.

{\bf Edit} Sorry Paradoxical answers are paradoxical, not false. We therefore need to treat them as uncertain answers: eg. to the best of Derek's knowledge the doctor can answer yes' orno' even if it is paradoxical rather than true or false.