45
$\begingroup$

I was working my way through some Knight and Knave Puzzles in Discrete Maths by Rosen, when I came across the following question:

Four friends have been identified as suspects for an unauthorized 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 that I did it.”

If the authorities also know that exactly one of the four suspects is telling the truth, who did it? Explain

Book solution:

John did it

My question:

Why is this so?

$\endgroup$
  • 25
    $\begingroup$ They don't seem like very good friends to me. $\endgroup$ – Larry OBrien Jan 3 '15 at 3:42
  • 15
    $\begingroup$ @LarryOBrien: Indeed. Friends would have chosen a set of statements such that knowing how many of them were telling the truth doesn't lead to a unique solution. I guess it's possible they were genuinely friends, but rubbish at logic, so they messed it up. It's a common error made by protagonists of logic puzzles, now I come to think of it. $\endgroup$ – Steve Jessop Jan 3 '15 at 4:38
  • $\begingroup$ Formulation of this is unclear: "If the authorities also know that exactly one of the four suspects is telling the truth" this doesn't really mean it's one and only one (truthspeaking == 1) who is telling truth. It rather say it's one or more of them who is telling truth (truthspeaking >= 1). I think that sentence needs a fix, otherwise it has no solutions :o $\endgroup$ – Petr Jan 7 '15 at 8:44
  • $\begingroup$ I mean if the sentence said: "If the authorities also know that only one of the four suspects is telling the truth and others are lying" the solution would come up easily $\endgroup$ – Petr Jan 7 '15 at 8:45
  • $\begingroup$ Hey, I remember seeing this exact riddle in a sidequest in Borderlands 2 (but with the perpetrator having stolen cash rather than hacked a computer). Guess the writers were more clever than I thought. $\endgroup$ – Hugo Zink Sep 16 '15 at 13:15

10 Answers 10

46
$\begingroup$

There's a logical inconsistency for the other options.

If we say that Alice is the one telling the truth, then Carlos is guilty, and he's lying about Diana, BUT that means Diana is telling the truth. We can only have one truth teller, so Alice must be lying.

It's a similar situation if we say John is telling the truth. Again, that leaves either Carlos or Diana also telling the truth.

If Carlos is telling the truth, then Diana is guilty. In this case John is also telling the truth. (I'm making the assumption that we can't have two guilty parties.)

Only Diana can be the one truth teller. In this case, Alice is lying about Carlos' guilt, Carlos is lying about Diana's guilt, and John is lying about his innocence. He did it.

$\endgroup$
41
$\begingroup$

The easiest way to approach the problem is to identify mutually contradictory statements, which off course are

  • Carlos said “Diana did it.”
  • Diana said “Carlos lied when he said that I did it.”

and to ascertain these statements is to realize that one of them is telling the truth. So this would also mean the rest of the two statements are false

  • Alice said “Carlos did it.”
  • John said “I did not do it.”

From which we can easily conclude that the statement "John said 'I did not do it.'" is false.

So John is the hacker.

$\endgroup$
  • 8
    $\begingroup$ The contradiction is the first thing I noticed; this is my favorite solution by far. $\endgroup$ – Steven Stadnicki Dec 31 '14 at 19:44
21
$\begingroup$

Solving by machine (this is overkill but fun, and as I am on a Prolog refresher...)

Code can be run online in SWI-Prolog using SWISH

% Define the persons

persons([alice,john,carlos,diana]).

% Define the statements of the persons

says(alice  , hacker(carlos)).
says(john   , not(hacker(john))).
says(carlos , hacker(diana)).
says(diana  , lies(carlos)).

% Main predicate. This is run by executing "?- solve(X)"

solve(Hacker) :- 
    selectTruthteller(TT),
    buildWorld(TT,World),    
    simplifyWorld(World,SW),   % run one simplification (this turns out to be enough, no second round needed)
    sort(SW,SimpleWorld),      % sort and remove duplicates from SW, yielding SimpleWorld
    writeln(SimpleWorld),      % write SimpleWorld
    isConsistent(SimpleWorld,Hacker). % check that SimpleWorld is consistent; if yes, the program succeeds and prints the "Hacker"

% Select a person as "truthteller". Assuming that person is the truthteller, consequences will be checked

selectTruthteller(TT) :- persons(Persons),member(TT,Persons).

% buildWorld(+Truthteller,-WorldOut).
% Generate "WorldOut" (which is a list of statements) under assumption that "Truthteller" is the truthteller
% We need to iterate over the "Persons", so we need to have a second buildWorld/3 predicate in addition to buildWorld/2 

buildWorld(TT,WorldOut) :- persons(Persons), buildWorld(TT,WorldOut,Persons).

% buildWorld(+Truthteller,-WorldOut, +ListOfPersons).
% If there are no persons left in the "ListOfPersons" we are done and the "WorldOut" is empty
% If the next person in the "ListOfPersons" is the truthteller, we add the statement that he/she "truthes" as well as his/her
% statement as gospel truth to the "WorldOut"
% % If the next person in the "ListOfPersons" is NOT the truthteller, we add the statement that he/she "lies" as well as his/her
% statement as gospel falsity to the "WorldOut"

buildWorld(_,[],[]).
buildWorld(TT,[truthes(TT),Stmt|WorldOutRest],[TT|PersonsRest]) :- says(TT, Stmt), buildWorld(TT,WorldOutRest,PersonsRest).
buildWorld(TT,[lies(P),not(Stmt)|WorldOutRest],[P|PersonsRest]) :- P \== TT, says(P, Stmt), buildWorld(TT,WorldOutRest,PersonsRest).

% Go through the world statements and simplify every statement in turn; the second line drops a statement if
% simplifyStmt/2 results in the atom "null"

simplifyWorld([],[]).
simplifyWorld([In|InRest],OutRest)       :- simplifyStmt(In,null)            , simplifyWorld(InRest,OutRest).
simplifyWorld([In|InRest],[Out|OutRest]) :- simplifyStmt(In,Out),Out \== null, simplifyWorld(InRest,OutRest).

% Simplify a single statement by eliminating "not"; use red cuts to simplify code

simplifyStmt(not(not(S)),S)           :- !.
simplifyStmt(not(lies(S)),truthes(S)) :- !.
simplifyStmt(not(hacker(_)),null)     :- !.
simplifyStmt(S,S).

% Check world for consistency

isConsistent(World,Hacker) :- persons(Persons),
                              everyPersonLiesOrTruthes(World,Persons),
                              \+ someoneLiesAndTruthes(World),
                              \+ thereIsMoreThanOneHacker(World),
                              thereIsAHacker(World,Hacker).

% Helper predicates to check world for consistency

everyPersonLiesOrTruthes(_,[]).
everyPersonLiesOrTruthes(World,[P|Persons]) :- member(lies(P),World),    everyPersonLiesOrTruthes(World,Persons).
everyPersonLiesOrTruthes(World,[P|Persons]) :- member(truthes(P),World), everyPersonLiesOrTruthes(World,Persons).

someoneLiesAndTruthes(World)    :- member(lies(P),World),member(truthes(P),World).

thereIsMoreThanOneHacker(World) :- member(hacker(P1),World),member(hacker(P2),World),P1 \== P2.

thereIsAHacker(World,P)         :- member(hacker(P),World).

And now the moment of truth:

?- solve(X).

This prints the possible worlds and stops once a consistent world has been found:

Sample output

Yup, it's John. The computer says so!

$\endgroup$
  • 4
    $\begingroup$ I like the approach, I just wish the code were smaller. $\endgroup$ – Pharap Jan 1 '15 at 6:11
  • 2
    $\begingroup$ @Pharap I'm sure there is a smaller solution. My code always tends towards large, but hopefully easy to understand. $\endgroup$ – David Tonhofer Jan 1 '15 at 11:28
  • 1
    $\begingroup$ @DavidTonhofer A simpler approach would probably have been to make one program for each possible case. But I'm not well versed in Prolog, but I thought I'd have a quick read of a tutorial after this answer. One day I plan to experiment with it some day for game AI (or a variant of it). $\endgroup$ – Pharap Jan 1 '15 at 12:16
  • $\begingroup$ Well thanks a bunch , @DavidTonhofer . Though I am not proficient in Prolog , but appreciate your effort :) $\endgroup$ – pranav Jan 18 '15 at 4:34
10
$\begingroup$

I like to use truth tables to answer these kinds of questions. The truth table for this question is simplified because it's given that only one suspect is telling the truth (I'm assuming only one person committed the crime):

enter image description here

The first four columns show the suspects and the scenarios of who possibly lied and who possibly told the truth. The second four columns show what can be gleaned by assuming that the respective suspect is the only one who told the truth. Here are my comments on each row:

  1. Alice is telling the truth: This results in both Carlos and John being guilty. This is a contradiction based on my assumption.

  2. John is telling the truth: We can say that Diana did not do it because Carlos is lying, but that means that Diana would be telling the truth. Since we are assuming it is in fact only John that is telling the truth in this scenario, we have a contradiction.

  3. Carlos is telling the truth. This results in both John and Diana being guilth. This is a contradiction based on my assumption.

  4. Diana is telling the truth. This means that John is the criminal.

$\endgroup$
  • 1
    $\begingroup$ That is wonderful @user2023861 - Thanks :) $\endgroup$ – pranav Jan 3 '15 at 4:50
6
$\begingroup$

Consider following cases:

Carlos is lying
If Carlos is lying, Diana is telling truth. So Alice and John are also lying, which means John's statement "I did not do it" is a lie. So John did it. (Correct answer)

Both Carlos and Diana can not tell a lie at the same time as Diana's statement says, "Carlos is lying" (Not possible)

Carlos is not lying
If Carlos is speaking truth, John must be lying. Which means both John and Diana hacked the computer. Assuming there is just one culprit, this is not possible.

$\endgroup$
4
$\begingroup$

Here's how I approached it:

Step 1. If Alice's or Carlos's statement is true, then John's is also true. This eliminates Carlos & Diana as suspects, leaving Alice & John as possibilities.

Step 2. If Alice did it, then John and Diana are both telling the truth. This eliminates Alice as a suspect, leaving John.

$\endgroup$
4
$\begingroup$

Another way to approach it is using the fact that you not only know that only one of them is telling the truth, but also that there are enough information to solve the puzzle:

If John was telling the truth, his piece of information (“I did not do it.”) would not answer the question ("Who did it?"), so you can assume he is lying, which means he did it.

Of course this approach only works for puzzles, but I thought it would worth mentioning :o)

Attempt for a more detailed explanation as requested in the comments:

  • You know that you have enough information to solve the puzzle
  • You know that only one of the suspects is telling the truth

Now, imagine John is telling the truth:

  • He said "I didn't do it"
  • This would mean that one of the 3 others suspects did it
  • This is not enough information to solve the puzzle (since we want only one name)

Therefor, he must be lying, and someone else must be telling the truth.

But since he is lying, and he is saying "I didn't do it", it means "he didn't NOT do it", which can be simplified into "he did it".

Afterthought: alternatively, Carlos and Diana say the opposite of each other, so one of them has to tell the truth while the second is lying; knowing that only one of the four suspects is telling the truth, you can assume that the two others are lying (including John)

$\endgroup$
3
$\begingroup$

The authorities know that only one is telling the truth
This indicates the solution is revealed after figuring out which suspect is telling the truth.

Alice said “Carlos did it.”

1. Is Alice's statement true?
If Alice's satement were considered to be true it would mean Carlos did it, but John said he didn't do it which would make John's statement also true if Carlos did it. There can only be one true statement. So Alice is lying.

Carlos said “Diana did it.”

2. Is Carlos's statement true?
If Carlos's satement were considered to be true it would mean Diana did it, but John said he didn't do it which would make John's statement also true if Diana did it. There can only be one true statement. So Carlos is lying.

Diana said “Carlos lied when he said that I did it.”

3. Is Diana's statement true?
We already proved Carlos lied. So when Diana said “Carlos lied when he said that I did it.” Diana is telling the truth

John said “I did not do it.”

4. Is John's statement true?
We proved Diana is telling the truth. We know only one statement is true. So when John said “I did not do it.” he was lying and guilty.

$\endgroup$
2
$\begingroup$

Another solution, similar to Abhijit's:

John and Diana both say they did not do it, but only one can be right, so it has to be either of them.

That implies that one of them has to be right, and everybody else has to be wrong. That means Carlos must be wrong when he says Diana did it.

So it's John.

$\endgroup$
2
$\begingroup$

It can only be John.

If the authorities also know that exactly one of the four suspects is telling the truth, who did it?

This sentence implies, that we have 4 cases.

Case 1: A Tells the truth, the other 3 suspects are lying.

Case 2: B Tells the truth, the other 3 suspects are lying.

and so on..

In each case, except for case 2, John would be lying.

John said “I did not do it.” -> That would say that John is lying 3 out of 4 times. If we take a closer look to case 2, which would make John telling the truth, this would imply that he isn't guilty and the other suspects are lying.

Carlos did it -> lie

Diana did it -> lie

Carlos lied when he said that I did it. -> This is a difficult one. Does Diana know what Carlos is going to say? If she knows who is telling the truth, does she suppose that Carlos is going to lie about her? That would make Diana the only one telling the truth, but in this case, we expect all suspects to lie but John. We can conclude that Carlos is lying ->Diana did not do it. But also Diana is lying which would imply that carlos was actually telling the truth when its obvious he was lying. That doesn't make any sense to me.

This leads to the conclusion that Diana is telling the truth and this makes John the culprit, since this is the only case making sense.

$\endgroup$

protected by Community Jan 4 '15 at 7:08

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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