Two Detectives

A crime was committed in Puzzleton, and 8 possible suspects were identified. Working separately, two detectives (Albert and Brutus) each narrowed down the list to two names. They know that between them, they have three names on their lists and the name that is shared is the actual culprit.

The two detectives meet at the police station to compare notes and find out who the final suspect is, but they are not allowed to communicate unless a police officer is with them. How can they each learn who the culprit is without the police officer knowing? (The officer may know the culprit is one of two people, but should not have definite knowledge at the end of their conversation.)

Can a method be found if there were originally more or less than 8 names?

[How do they know they share a single name on their two lists? Why don't they meet somewhere other than the police station? Why can't the police officer be trusted? Why do the detectives' names conveniently begin with the first two letters of the alphabet? This is Puzzleton, where certain things just are, and should not be questioned... -KD]

Source: Bert Sevenhant, citing Vladomir Mascharouk, from White Russia (Belarus).

Solutions were received from Larry Baum. His solution works for any N>=8. Can a solution be found for N<8?

Larry's solution:

Detective 1 (D1), sorts the suspects (seemingly randomly) into pairs (s1,s2), (s3,s4), (s5,s6) (s7,s8) and tells D2 (and the PO) that one of the pairs is his, but not which one. D2's pair must be split between two of the given pairs, so he can choose one representative from each pair and form a set that has his pair in it, say and arrange them into a ring so that his two are adjacent, say (s1,s6,s3,s7) (s1 is next to s6 and s7, s6 is next to s1 and s3, etc.)

Now D1 knows the guilty suspect. He tells D2 it's one of two suspects (in random order of course): the guilty one and the one not adjacent. Now D2 knows but the PO only has it narrowed down to two suspects.

For example, suppose D1 knows it's s3 or s4 and D2 knows it's s3 or s7.

D1: "My pair is one of: (s1,s2), (s3,s4), (s5,s6) (s7,s8)
D2: "My pair is adjacent in the ring: (s1, s5, s7, s3)
D1 now knows it's s3 and that D2 has either (s3,s7) or (s1,s3)
D1: "The guilty person is either s5 or s3"

This works with any number > 8. D1 pairs them off (if n is odd he leaves out 1 suspect). D2 forms a ring with one from each pair (if the omitted suspect is one of his, this only helps since D2 knows immediately who is guilty) and D1 give D2 back a pair of non-adjacent suspects to choose from.

Mail to Ken