9
$\begingroup$

This is a variant of the puzzle here.

We have captured 5 spies belonging to a secret organization. Their identities are unknown; we only know them by their codenames A, B, C, D, and E. After thorough interrogation, here's what we've figured out:

  • Spy A claims to have worked with 4 of the other spies
  • Spy B claims to have worked with 3 of the other spies
  • Spy C claims to have worked with 3 of the other spies
  • Spy D claims to have worked with 2 of the other spies
  • Spy E claims to have worked with 1 of the other spies
  • A spy who lies will always lie by saying a bigger number than the true number
  • At most one spy is a liar, and it isn't C.

Questions:

  • Are any of the spies liars?
  • Have B and C worked together?
$\endgroup$
7
  • $\begingroup$ "If a spy is lying, he knows more people than he claims." You mean worked with more people? $\endgroup$ – new QOpenGLWidget Feb 13 at 17:48
  • $\begingroup$ The question was edited after closing. Now it seems a good question for this site. $\endgroup$ – justhalf Feb 14 at 5:12
  • $\begingroup$ If I would have more reputation I would have voted to reopen, I will agree with @justhalf, this question is now interesting. $\endgroup$ – Anonymous Feb 14 at 8:48
  • 1
    $\begingroup$ Same problem, but with 7 spies: www2.kenyon.edu/Depts/Math/Aydin/Problem/Past/Fall04/… $\endgroup$ – Nautilus Feb 14 at 12:16
  • 1
    $\begingroup$ @justhalf Puzzle was closed for lacking attribution. The rewording makes it far clearer now (thank you!) but I still don't see any proper attribution. $\endgroup$ – xhienne Feb 14 at 22:31
9
$\begingroup$

We can summarize this information in a graph, where the vertices are the 5 spies, and two spies are connected if they have worked together. Each spy's assertion is then a claim about the degree of the associated vertex.

Are any of the spies liars?

Yes, one of the spies has to be a liar. The sum of the degrees of vertices in a graph is twice the number of edges, and since the sum of the degrees asserted here is odd, one of the assertions must be false.

Have B and C worked together?

To answer this question, we first note that E is not lying. Otherwise E would never have worked with any of the other spies, meaning A can have only worked with at most 3 other spies, which would imply A is also lying.

Now if B and C have not worked together before, then C must have worked with A, D and E, because C is not a liar. Since E is not lying, E cannot have worked with A, which implies A is lying. But B can only have worked with A and D, which implies B is also lying. This is a contradiction, so B and C must have worked together.

$\endgroup$
3
  • $\begingroup$ A more elegant solution than mine. $\endgroup$ – Nautilus Feb 16 at 17:03
  • $\begingroup$ Can you possibly show a graph or a figure to explain the vertices, edges and degrees? I don't fully understand this. $\endgroup$ – Sid Feb 17 at 10:36
  • $\begingroup$ @Sid: The whole point of part 1 is that you cannot show a graph which has these properties. The handshaking lemma is the basic graph theory result being applied here. Hope the link helps! $\endgroup$ – Jeremy Dover Feb 17 at 14:27
2
$\begingroup$

I found some approach by drawing a graph of the spies from the lowest number (E = 1) to the highest (A = 4).

So at first we should talk about E. As it comes from the question E have worked with only 1 other spy. So lets see if he's lying or not. If E is lying then he should have never worked with any other spies so then A is also have worked with 3 others which breaks the rules where the question saying At most 1 spy is lying. Therefore E is NOT lying.

Now we move to D. If we consider D as the liar then our graph would be something like the follow, that makes the C or B a liar too. So D is NOT a liar too:

enter image description here

Ok now we get to check if B is a liar or not. As A is the last spy standing so he shouldn't be a liar so the graph would be like this. Considering the following graph one answer is that B is lying:

enter image description here

The question also have another answer but it doesn't mean there is 2 spies lying. As it comes from the question we understand that there might be more than one answer. it says

Are there any spies

As we check A if he is lying or not we can see that A is lying in 2 like below:

enter image description here

And about the second question which asks if B and C have ever worked together or not we can see that C as the never lying spy will have worked with A, E and D and since E will only work with 1 spy so then E and A would have never worked together and that breaks the rule which says only one spy is lying.

$\endgroup$
1
$\begingroup$

The sum of the stated numbers is 4+3+3+2+1 = 13, which is odd, meaning there's a liar.

If Spy A has worked with 4 players, an odd number must turn even or vice versa:

A: AB, AC, AD, AE
B: 3 or 2 spies (one of them being BA, so not zero)
C: 3 spies (one of them being CA)
D: 2 spies or 1 spy (one of them being DA)
E: 1 spy (one of them being EA, so not zero).

None other than A has worked with E, so C must have worked with A, B and D.

If Spy A has worked with fewer than 4 players, the rest of the stated numbers are all true:

A: 3 spies or 1 spy
B: 3 spies
C: 3 spies
D: 2 spies
E: 1 spy.

For B and C to not have worked with each other, they must have worked with A, D and E, but E can't have worked with more spies than one.

In conclusion, B must have worked with C in any case.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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