This puzzle is taken from the book Mathematical puzzles: a connoisseur's collection by P. Winkler.
Two sheriffs in neighboring towns are on the track of a killer, in a
case involving eight suspects. By virtue of independent, reliable
detective work, each has narrowed his list to only two. Now they are
engaged in a telephone call; their object is to compare information,
and if their pairs overlap in just one suspect, to identify the killer.The difficulty is that their telephone line has been tapped by
the local lynch mob, who know the original list of suspects but not
which pairs the sheriffs have arrived at. If they are able to identify
the killer with certainty as a result of the phone call, he will be
lynched before he can be arrested.Can the sheriffs, who have never met, conduct their conversation
in such a way that they both end up knowing who the killer is (when
possible), yet the lynch mob is still left in the dark?
It has different solutions. But the question is why this puzzle is unsolvable for seven suspects?
Original problem was discussed at Puzzling. There are some solutions here.
EDT. Let me summarize the discussion from comments.
-
Formal success conditions (due to usul): "A deterministic communication protocol such that, for any singly-overlapping sets held by the sheriffs, the sheriffs always deduce the correct suspect, and the mob has no deterministic strategy to always guess the correct suspect."
-
It is a mathematical problem. Original problem has absolutely consistent solution. (It does not use any cryptographic assumptions.)
-
Puzzling solution is wrong and the number of suspects is important here.
-
(Due to usul.) This problem is very close to many types of problems in CS, such as zero-knowledge proofs and secure multiparty communication, but so far it is not clear if exactly this type of problem being studied.
Best Answer
Here's a solution for the case of seven suspects that uses the Fano plane. Let the seven points of the Fano plane represent the seven suspects. Alice and Bob both reveal the name of the suspect completing a line with the two suspects on their list. There are now two cases to consider:
Alice and Bob did not name suspects on each other's lists. Then the suspicion (among the sheriffs) is reduced to the four suspects not named and not completing a line with the two suspects named. Alice knows that Bob is uncertain if Alice's list is the list which is correct or its complement. Same for Bob. Alice reveals her list. Bob reveals his. Both now know the culprit. Eve would also know, assuming she knew that we are in case 1, but she doesn't.
Alice named one of Bob's suspects, and since we are assuming their suspect lists have an intersection of size 1, Bob named one of Alice's suspects. Both sheriffs know this, but Eve doesn't. Also, both sheriffs now know who the culprit is. The rest of the conversation is only in order to not reveal to Eve that case 2 is occurring. Alice names two suspects that make a line with her first-announced suspect, but don't include Bob's first-announced suspect. Bob does the same.
The protocol is not deterministic when it falls into case 2, requiring arbitrary choice, but I fail to see why you want determinism.