We have captured 5 spies. Their names are A, B, C, D, and E

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?
• "If a spy is lying, he knows more people than he claims." You mean worked with more people? Feb 13 at 17:48
• The question was edited after closing. Now it seems a good question for this site. Feb 14 at 5:12
• If I would have more reputation I would have voted to reopen, I will agree with @justhalf, this question is now interesting. Feb 14 at 8:48
• Same problem, but with 7 spies: www2.kenyon.edu/Depts/Math/Aydin/Problem/Past/Fall04/… Feb 14 at 12:16
• @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. Feb 14 at 22:31

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.

• A more elegant solution than mine. Feb 16 at 17:03
• Can you possibly show a graph or a figure to explain the vertices, edges and degrees? I don't fully understand this.
– Sid
Feb 17 at 10:36
• @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! Feb 17 at 14:27

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:

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:

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:

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.

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:

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.