Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Here's a puzzle:

Four friends have been identified as suspects for an authorized access into a computer system. They have made statements to the investigating authorities. Alice said "Carlos did it." John said "I did not do it." Carlos said "Diana did it." Diana said "Carlos lied when he said I did it."

(a) If the authorities also know that exactly one of the four suspects is telling the truth, who did it? Explain your reasoning. (b) If the authorities also know that exactly one of them is lying, who did it? Explain your reasoning.

We can list the propositions as follows:

$p$: "Carlos did it"

$q$: "I did not do it"

$r$: "Diana did it"

$s$: "Carlos lied when he said Diana did it"

It becomes reasonable to assume, then, that $p \rightarrow \neg r$, $p \rightarrow q$, and $r \oplus s$.

Now, I'm interested in whether there is a more elegant way to come to the conclusion of parts a) and b), using only logical equivalencies, rather than adding a conjunction between all the assumptions above and the four possible arrangements:

a) $(p \vee \neg q \vee \neg r \vee \neg s) \vee (\neg p \vee q \vee \neg r \vee \neg s) \vee...$

b) Inverse of a).

and simplifying until you get down to the four letters themselves (in which their truth values will become apparent).

If we follow this method the solution is long and error-prone, but ultimately works. Any other ideas on how to accomplish this only using logical equivalencies?

Thanks.

share|improve this question

3 Answers 3

Since you asked for a solution "only using logical equivalencies", here is how I would solve this. You will see how the solution is almost mechanical: after the formalization, a large part is just simplification using the laws of logic.

Let's call the four involved persons $\;a,j,c,d\;$ (obviously these are distinct), and we know that exactly one of them is the hacker $\;h\;$. Writing $\;T(x)\;$ for "$\;x\;$ speaks the truth", then we can translate the four persons' statements to

\begin{align} T(a) \equiv & h = c \tag{0} \\ T(j) \equiv & h \ne j \tag{1} \\ T(c) \equiv & h = d \tag{2} \\ T(d) \equiv & \lnot T(c) \tag{3} \\ \end{align}

For part (a), we try to simplify the condition using the above statements:

\begin{align} & \text{exactly 1 of }T(a),\,T(j),\,T(c),\,T(d)\text{ is true} \\ \equiv & \qquad\text{"using (3), which says that exactly one of $\;T(c),\,T(d)\;$ is true"} \\ & \text{exactly 0 of }T(a),\,T(j)\text{ is true} \\ \equiv & \qquad\text{"rephrase"} \\ & \lnot T(a) \land \lnot T(j) \\ \equiv & \qquad\text{"using (0) and (1)"} \\ & h \ne c \land h = j \\ \equiv & \qquad\text{"use right conjunct in left"} \\ & j \ne c \land h = j \\ \equiv & \qquad\text{"$\;j \ne c\;$ since these are distinct persons; simplify"} \\ & h = j \\ \end{align} So John is the hacker (and we did not need $(2)$).

For part (b), the calculation is very similar:

\begin{align} & \text{exactly 1 of }T(a),\,T(j),\,T(c),\,T(d)\text{ is false} \\ \equiv & \qquad\text{"using (3), which says that exactly one of $\;T(c),\,T(d)\;$ is false"} \\ & \text{exactly 0 of }T(a),\,T(j)\text{ is false} \\ \equiv & \qquad\text{"rephrase"} \\ & T(a) \land T(j) \\ \equiv & \qquad\text{"using (0) and (1)"} \\ & h = c \land h \ne j \\ \equiv & \qquad\text{"use left conjunct in right"} \\ & h = c \land c \ne j \\ \equiv & \qquad\text{"$\;c \ne j\;$ since these are distinct persons; simplify"} \\ & h = c \\ \end{align} In this case Carlos is the hacker (and again we did not need his statement $(2)$).

share|improve this answer

In the spirit of Ross' answer the same logic can be used for if only one person is lying. If Diana is lying, both she and Carlos (according to Alice) are guilty. If Carlos is lying, everyone else is telling the truth and Carlos is your only culprit.

share|improve this answer

In this case, since Carlos and Diana contradict each other, one must be the truth-teller. If Carlos is telling the truth, John is lying and you have two culprits. So Diana is the truth teller, John lied and is the culprit.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.