“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.
Answer
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:
- $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}$.
- $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}.
No comments:
Post a Comment