Rompecabezas de "Los dos sheriffs"

Question

Este rompecabezas es tomado del libro de problemas Matemáticos: un conocedor de la colección por P. Winkler.

Dos alguaciles en los pueblos vecinos están en la pista de un asesino, en un el caso que involucra a ocho sospechosos. En virtud de independiente, confiable trabajo de detective, cada uno ha reducido su lista a sólo dos. Ahora son participando en una llamada telefónica; su objeto es comparar la información, y si sus parejas se superponen en un solo sospechoso, para identificar al asesino.

La dificultad es que su línea telefónica ha sido aprovechado por el local de lynch mob, que conocen el original de la lista de sospechosos, pero no que los pares de los presidentes han llegado. Si son capaces de identificar el asesino con certeza como resultado de la llamada de teléfono, que será linchado, antes de ser arrestado.

Puede el alguacil, a los que nunca han conocido, llevar a cabo su conversación de tal manera que ambos terminan sabiendo que el asesino es (cuando posible), sin embargo, la lynch mob todavía queda en la oscuridad?

Se dispone de diferentes soluciones. Pero la pregunta es ¿por qué este rompecabezas es irresoluble para los siete sospechosos?

Problema Original se discutió en el Desconcierto. Hay algunas soluciones aquí.

EDT. Permítanme resumir la discusión de los comentarios.

1. Formal de las condiciones de éxito (debido a usul): "Un determinista protocolo de comunicación tal que, para cualquier solos superposición de conjuntos celebrado por los alguaciles, los presidentes siempre deducir la correcta sospechoso, y la mafia no tiene estrategia determinista siempre adivinar la correcta sospechoso".

2. Se trata de un problema de matemática. Problema Original no tiene absolutamente solución consistente. (No utilizar cualquiera de cifrado supuestos.)

3. Desconcertante solución es incorrecta y el número de sospechosos es importante aquí.

4. (Debido a usul.) Este problema está muy cerca de muchos tipos de problemas en el CS, tales como cero-conocimiento de las pruebas y seguro multipartidario de comunicación, pero hasta ahora no está claro si exactamente este tipo de problema que se estudia.

Answer 1

He aquí una solución para el caso de siete sospechosos que se utiliza el plano de Fano. Deje que los siete puntos del plano de Fano representan a los siete sospechosos. Alice y Bob ambos revelan el nombre de la sospecha de completar una línea con los dos sospechosos en su lista. Ahora hay dos casos a considerar:

1. Alice y Bob no el nombre de los sospechosos en cada una de las otras listas. A continuación, la sospecha (entre los sheriffs) es reducido a cuatro sospechosos que no se nombra y que no se complete una línea con los dos sospechosos nombre. Alice sabe que Bob es incierto si Alice es la lista de lo que es correcto o su complemento. Mismo para Bob. Alice revela su lista. Bob revela su. Ambos saben ahora el culpable. Eva, además de conocer, asumiendo que ella sabía que estamos en el caso 1, pero ella no.

2. Alice nombrado uno de Bob sospechosos, y ya que estamos suponiendo que el sospechoso listas tienen una intersección de tamaño 1, Bob nombrado uno de Alice a los sospechosos. Tanto los sheriffs de saber esto, pero Eva no. También, tanto los sheriffs ahora sabemos que el culpable es. El resto de la conversación es sólo con el fin de no revelar a Eva de que el caso 2 se está produciendo. Alice nombres de los dos sospechosos que hacer una línea con su primer anunció de sospecha, pero no incluye el de Bob primero-anunció sospechoso. Bob, ¿el mismo.

El protocolo no es determinista cuando se cae en el caso 2, que requieren de una elección arbitraria, pero no veo por qué quieres determinismo.