Two Sheriffs and Eavesdroppers - 2

“The Two Sheriffs” puzzle was already discussed here Two Sheriffs and Eavesdroppers. This puzzle has only one difference: we have seven suspects instead of eight.

Two sheriffs in neighboring towns are on the track of a killer, in a case involving seven 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?

Original problem is takken from: Mathematical Puzzles, a Connoisseur's Collection, Peter Winkler. The solution for seven suspects belongs to Yoav Kallus.

• Can't the sheriffs just use public-key encryption to say whatever they want to each other? – Ben Aaronson Apr 22 '15 at 16:27
• @BenAaronson Every public key protocol can be decoded (given enough time). These rely on functions which are hard to invert, not impossible. – Mike Earnest Apr 22 '15 at 17:33
• @MikeEarnest Good point, though surely the sherrifs won't be that slow to arrest the guy – Ben Aaronson Apr 22 '15 at 17:59

Assign each suspect a number $1-7$. Define the xor of two numbers between $1$ and $7$ as follows: write them in binary, then xor them together bitwise. For example, $3 \oplus 6=011\oplus 110=101=5$.

Some observations:

• $a\oplus b$ is different from both $a$ and $b$.

• If $a\oplus b=c$ and $d\oplus e=f$, then the sets $\{a,b,c\}$ and $\{d,e,f\}$ have an element in common. This can be verified by checking the only sets of three numbers where two of them xor together to make the other are {1,2,3},{1,4,5},{1,6,7},{2,4,6},{3,4,7},{3,5,6},{2,5,7}, and that any two of these intersect.

The converstion: Lets say Alice has {a,b} and Bob has {a,c}. Alice announces $a\oplus b$ and Bob announces $a\oplus c$. If Alice and Bob say the same thing, then they know they have the same pair, and hang up. If not, there are two possibilities:

1. $a\oplus b\neq c$. Then it also follows that $a\oplus c\neq b$, so neither Sheriff said a number in the others list. In this case, they each announce their pair, ${a,b}$ and ${a,c}$.
2. $a\oplus b=c$, which also implies $a\oplus c=b$. They now each say a random pair whose xor is what they first announced, except for their actual pair.

Why the sheriffs know the killer: It's easy to see why they do in case 1, since they each heard the other's pair. In case, 2, when Alice hears Bob say $b$, she knows $b$ is not the killer, so it is $a$. Same thing happens for Bob.

Why the lynch mob doesn't: Suppose that they hear the numbers $a_1$ and $b_1$, followed by the pairs ${a_2,a_3}$ and ${b_2,b_3}$. It could be the case that Alice had the pair ${a_2,a_3}$ and Bob has the pair ${b_2,b_3}$, in which case the killer would be the intersection of these sets (this would be case 1). However, it could also be the case that Alice had $\{a_1\oplus b_1,b_1\}$ and Bob had $\{a_1\oplus b_1,a_1\}$. Here we are in case 2, where Alice and Bob just randomly chose to say $\{a_2,a_3\}$ and $\{b_2,b_3\}$. No matter what sets they randomly announced, by bullet point 2, they will always intersect, so this is really indistinguishable from case 1.

For example, here are two situations where the Sheriffs have the same conversation, but the killer is a different person.

• Alice has {1,2}, while Bob has {1,5}. Alice says 3, Bob says 4. Since 4 is not in {1,2} and 3 is not in {1,5}, we are in the first bullet point. They then each announce their lists, {1,2} and {1,5}. They now both know that the killer is 1.

• Alice has {4,7}, Sheriff 2 has {3,7}. Alice says 3, Bob says 4. Each number is in the other's list, we are in the second bullet point. They know now the killer is 7. Alice randomly announces one of the pairs {1,2} or {5,6}, since these are the pairs which xor together to make 3 (besides {4,7}). Let's say she chooses {1,2}. Similarly, Bob randomly says one of {1,5}, or {2,6}, and he randomly chooses {1,5}.

Solution:

If one sheriff outright states that one suspect is not on his list then the problem resembles the original problem with eight. In the special case that the first sheriff eliminates a suspect who is on the list of the second sheriff, then the second sheriff (knowing that one of his suspects is innocent) replaces the removed suspect with a random other suspect.

Lets say S1 has list {a,b} and S2 has list {a,c}.S1 says: I know with certainty that d is not guilty. My list is one of the following: {a,b},{c,e},{f,g}.

S2 says: My list is one of the following: {a,c},{b,f},{e,g}

S1 now knows that S2 has either {a,c} or {b,f}

S1 says: The criminal is either in the set {a,f} or {b,g}

As criminal c is now excluded, S2 knows that the criminal is a so he says: the criminal is in the set {a,g}

S1 now knows that the criminal is a.

• This does not work if the random suspect the second sheriff chooses makes his pair identical to the first sheriff. – Ian MacDonald Apr 22 '15 at 12:11
• When S1 says the criminal is in the set {a,f} or {b,g}, they don't know that they needed to eliminate c and not f. Without knowing, we must also consider that they say {a,e} or {b,c} instead. In which case the rest of your solution fails. – Yoav Kallus Apr 22 '15 at 13:26
• @Yoav, $S_1$ knows that he should eliminate c because his suspect list is $\{a,b\}$. – Ian MacDonald Apr 22 '15 at 17:02
• @IanMacDonald How could that possibly happen? If I understand it correctly, the first sheriff tells the second one his three pairs before the second one makes his "random" choice? – No. 7892142 Apr 23 '15 at 7:26

This builds on @Poelie's answer a little, and should take care of the case where that didn't work

Suspects: {a,b,c,d,e,f,g}
Sheriff 1's shortlist: (a,b)

Start by reducing the problem to an even number of suspects
Sheriff 1 says 'g is innocent'
If Sheriff 2 responds 'That's odd, I had them as a suspect':
- Sheriff 1 asks 'Which of {a,d} and {b,e} contains your other suspect'?
- The answer reveals the culprit to the sheriffs, but leaves the mob with two suspects

In the more likely scenario that g is not one of Sheriff 2's suspects:
- S1 posits three shortlists: {a,b},{c,d},{e,f}
- S2 posits three shortlists: {a,c},{b,e},{d,f)
- Knowing the culprit is either a or b, S1 knows that S2's list is either {a,c} or {b,e}
- S1 says the culprit is either in {a,e} or {b,f}
-- If S2 has {a,c}, this tells them that a is the culprit, and they say the culprit is in {a,f}
-- If S2 has {b,e}, they agree that the culprit is in one of the two groups, and this tells S1 that the culprit is b
-- There's one more step here, but I haven't worked it out yet
- Again, the sheriffs know the culprit, but the mob is left with two possible answers

It occurs to me that this only really works if we take it as read that the sheriffs have different shortlists with one member's overlap. But I've typed it all out now, and it should make sense for that case.

• Unfortunately, when S1 says the criminal is in either {a,d} or {b,f}, they are unwittingly tipping the mob off to the fact {a,b} was their list: that's the only pair from the original list with both elements represented in the new lists. Since we are assuming the mob knows the detail of the protocol (e.g. sheriffs can't simply speak in code), the mob knows that the pair satisfying that criterion is S1's list. – Yoav Kallus Apr 22 '15 at 15:29
• You're right... Hmm. Think I need to manipulate the shortlists suggested by sheriff 2 for this to work properly. – LogicianWithAHat Apr 22 '15 at 16:01