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.

`>!`

to hide it until you mouse over it. $\endgroup$ – Douglas Zare Apr 17 '15 at 15:13