KGS math club/solution 11 26
(There is an example in the end. The solution might be easier to follow if reading the example in parallel with the solution.)
Let's call the sheriffs A and B. First, A announces four pairs from the publicly known list and says that her short list is one of these four pairs. A picks one pair as her real short list and picks the three remaining pairs randomly; she announces the pairs in random order.
If the short list of B is among the pairs A announced, B can tell A that they have the same short list and that they do not know the murderer.
If the short list of B is divided among the pairs A announced, B announces two pairs and says his short list is either of those. One pair is his real short list and for the other pair he picks one random suspect from each of the pairs A announced that didn't have B's suspects in them. B announces the two pairs in random order.
Now A knows that the murderer is the one suspect from her short list that is on the two pairs B announced (the other one isn't there because B picked just one suspect from each of A's pairs). A announces one last pair in random order: one member is the suspect A knows is the murderer and the other member is a random pick from the other pair B announced (which didn't have the murderer). A says the murderer is among these two.
Now B also knows who the murderer is, since the other suspect A mentioned isn't in his short list.
The public, however, doesn't know which one is the murderer. The selection of the pairs has been apparently random so that new pairs have been formed from old pairs by selecting one member from each pair and pairing them up. If the actual murderer was the other member of the last pair the exact same naming of pairs could have occurred.
(This is not a rigorous solution but the details should be easy enough to fill in.)
Example:
Suspects 1-8. A's short list 1 & 2, B's short list 1 & 3.
A announces pairs 56, 12, 34, 78.
B announces pairs 13, 68.
A announces pair 18.
Now both know the murderer is suspect 1. However, if short lists were 7 & 8 for A and 6 & 8 for B the exact same process could have occurred, so the public doesn't know whether the murderer was suspect 1 or 8. This example is isomorphic with all cases where the short lists are different from each other.
