35
$\begingroup$

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.

  1. 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."

  2. It is a mathematical problem. Original problem has absolutely consistent solution. (It does not use any cryptographic assumptions.)

  3. Puzzling solution is wrong and the number of suspects is important here.

  4. (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.

Improve this question
$\endgroup$
25
  • 14
    $\begingroup$ Your question is perhaps more suitable for the puzzling stack exchange website? $\endgroup$
    – coudy
    Commented Apr 17, 2015 at 12:39
  • 6
    $\begingroup$ What are the rules governing their conversation? If they can simply use public-key cryptography, then the problem is not particularly interesting! $\endgroup$
    – James Cranch
    Commented Apr 17, 2015 at 14:55
  • 3
    $\begingroup$ I think there is a valid mathematical question here that is better asked either here or MSE, depending on what level it is, rather than on a puzzle site. However, to fit MO, you should at least link to what is known. You can use a spoiler mark-up: Start each paragraph with >! to hide it until you mouse over it. $\endgroup$
    – Douglas Zare
    Commented Apr 17, 2015 at 15:13
  • 4
    $\begingroup$ Clearly the lynch mob can break public-key cryptography, so you can't use it. $\endgroup$
    – Yakky
    Commented Apr 17, 2015 at 17:20
  • 4
    $\begingroup$ Privacy-preserving joint computation is an important, and increasingly relevant problem in computer science. I don't know the state of knowledge about the set intersection problem, but you should check out the following papers: dx.doi.org/10.1007/978-3-540-24676-3_1 and dx.doi.org/10.1007/978-3-642-14577-3_13 $\endgroup$
    – Yoav Kallus
    Commented Apr 17, 2015 at 17:47

1 Answer 1

Reset to default
48
$\begingroup$

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:

  1. 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.

  2. 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.

Improve this answer
$\endgroup$
13
  • 3
    $\begingroup$ Re your last sentence, but the protocol can be made deterministic by making one of the arbitrary choices. $\endgroup$
    – usul
    Commented Apr 18, 2015 at 20:57
  • 5
    $\begingroup$ Brilliant to use the Fano plane! $\endgroup$
    – Joseph O'Rourke
    Commented Apr 18, 2015 at 21:02
  • 2
    $\begingroup$ @HarryAltman Bob does not need to be careful since there will always be exactly one point of intersection for all four possible choices of the last steps. $\endgroup$
    – Tony Huynh
    Commented Apr 18, 2015 at 23:27
  • 5
    $\begingroup$ @usul, I don't think it can. Note that from Eve's point of view after Alice and Bob's first announcements, one instance of case 2 can match four different instances of case 1. If Alice and Bob have a deterministic choice in case 2, then they have to pick a single instance of case 1 to mimic, which means that the other three instances are never mimicked and always correspond to case 1. $\endgroup$
    – Yoav Kallus
    Commented Apr 19, 2015 at 0:49
  • 1
    $\begingroup$ @AntonPetrunin Good question (I see now it was also raise by disznoperzselo in the comments to the question). It would be nice to have a solution where Eve's best guess is correct with a lower probability, but I don't see how to adapt this solution in that direction. I don't see any reason that the probability couldn't be improved, but maybe the improved protocol will not be as nice and symmetric. $\endgroup$
    – Yoav Kallus
    Commented Nov 14, 2021 at 20:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .