Two sheriffs are working on a case to find one culprit. There were initially 8 suspects; through independent work, each sheriff has narrowed this down to a list of 2. Because they are good sheriffs, they can be sure that both of their lists contain the culprit. They plan to make a phone call tonight to see if they can combine their information to find the culprit. However, the locals (who know the 8 suspects, but neither of the narrowed lists) have tapped their phone line. If the locals can figure out the culprit based on this phone call, then they will lynch him before he can be brought to justice.
How can the sheriffs conduct their conversation so that they can both deduce the culprit, when possible*, but the locals can't?
*If the sheriffs have the same list of 2 suspects, then they won't be able to deduce the culprit. As long as their lists are different, they can. The lists cannot be disjoint, since they both contain the unique culprit.
Source: Mathematical Puzzles, a Connoisseur's Collection, Peter Winkler
Answer
Let's say S1 has the list {a,b} and say S2 has {a,c}.
S1: {a,b}, {c,d}, {e,f}, {g,h} - one of these is my list.
S2: {a,c}, {b,d}, {e,g}, {f,h} - one of these is mine.
Now both S1,S2 know their sets are inside {a,b,c,d}, whereas because of symmetry, it could be {e,f,g,h} or {a,b,c,d} as far as eavesdroppers are concerned.
So S1 and S2 play a game revealing info but keeping this info symmetric in the other set too.
S1: {a,e}, {b,f} - These lists have my suspects. S2: Knows the culprit is a (since he knows S1's set now).
S2: {a,e} - The culprit is in this list. S1: Knows the culprit is a.
Each time, the eavesdroppers can't distinguish between the two sets; finally they can't distinguish between a and e.
No comments:
Post a Comment