46
$\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?

Improve this question
$\endgroup$
5
  • 27
    $\begingroup$ They don't seem like very good friends to me. $\endgroup$
    – Larry OBrien
    Jan 3, 2015 at 3:42
  • 16
    $\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, 2015 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, 2015 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, 2015 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
    Sep 16, 2015 at 13:15

10 Answers 10

Reset to default
48
$\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.

Improve this answer
$\endgroup$
0
44
$\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.

Improve this answer
$\endgroup$
1
  • 9
    $\begingroup$ The contradiction is the first thing I noticed; this is my favorite solution by far. $\endgroup$
    – Steven Stadnicki
    Dec 31, 2014 at 19:44
21
$\begingroup$

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

The code can also be found at github

Run it on your machine if you have a Prolog or online in SWISH which is based on SWI-Prolog

% https://puzzling.stackexchange.com/questions/6552/puzzle-who-hacked-the-computer
%
% ===
% 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
% ===


% 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. We will call this later

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, logical 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).

After starting a Prolog interpreter and loading the code from file who_is_the_hacker.pl (for example), the moment of truth. This prints the possible worlds and stops once a consistent world has been found

?- [who_is_the_hacker].
true.

?- solve(X).
[hacker(carlos),hacker(john),lies(carlos),lies(diana),lies(john),truthes(alice),truthes(carlos)]
[lies(alice),lies(carlos),lies(diana),truthes(carlos),truthes(john)]
[hacker(diana),hacker(john),lies(alice),lies(diana),lies(john),truthes(carlos)]
[hacker(john),lies(alice),lies(carlos),lies(john),truthes(diana)]
X = john ;  % john is the hacker but maybe there are more solutions
false.      % no, there is only one solution

In case one is using SWISH, this can be seen:

Sample output

Improve this answer
$\endgroup$
4
  • 4
    $\begingroup$ I like the approach, I just wish the code were smaller. $\endgroup$
    – Pharap
    Jan 1, 2015 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, 2015 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, 2015 at 12:16
  • $\begingroup$ Well thanks a bunch , @DavidTonhofer . Though I am not proficient in Prolog , but appreciate your effort :) $\endgroup$
    – pranav
    Jan 18, 2015 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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ That is wonderful @user2023861 - Thanks :) $\endgroup$
    – pranav
    Jan 3, 2015 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.

Improve this answer
$\endgroup$
0
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.

Improve this answer
$\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)

Improve this answer
$\endgroup$
0
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.

Improve this answer
$\endgroup$
0
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.

Improve this answer
$\endgroup$
0
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.

Improve this answer
$\endgroup$

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