Espías en Puzzlevania
Lo que voy a decirles no sale de esta habitación. Durante el año pasado, nos preocuparon los sucesos en la nación de Puzzlevania. Creemos que un ataque mayor puede ser inminente. Sin embargo, el general se niega a actuar sin pruebas más concretas de amenaza. Con ese fin, nos estamos preparando para enviar 16 espías y un maestro de espías a Puzzlevania para un mayor reconocimiento y evaluación de amenazas. Pero hay una trampa.
Cada agente debe compartir sus hallazgos con los otros 16 para asegurarse de que todos puedan seguir el plan de contingencia adecuado. Nuestra gente ha desarrollado un código tal que cualquier mensaje parece inocuo (y sin galimatías) para un observador común. Desafortunadamente, me acaban de informar que Puzzlevania tiene un nuevo dispositivo que podrá descifrar nuestro código con solo 10 muestras únicas.
Enviar comunicaciones electrónicas es demasiado arriesgado dado este dispositivo. Nuestra única esperanza es confiar en el sistema de correo tradicional de Puzzlevania. El correo normalmente se recoge un día, permanece en el centro postal durante la noche y luego se entrega al día siguiente (Puzzlevania no es tan grande, por lo que solo hay un centro postal). Sin embargo, a veces el correo permanece varias noches, pero finalmente se entrega todo el correo.
Los inspectores del gobierno pueden aparecer por la noche con el dispositivo de descifrado de códigos y hacer que escanee cada correo en el centro. Luego vuelven a sellar perfectamente todo el correo y se van. Afortunadamente, otras fuentes indican que solo tienen el presupuesto para dos inspecciones más este año, y la antigua costumbre prohíbe buscar el correo enviado mientras no tienen presupuesto (incluso si reciben más después).
Necesito que elabore un plan para garantizar que todos los agentes puedan enviar sus hallazgos a los demás sin que Puzzlevania rompa el código. Puede suponer que el maestro de espías comienza cualquier cadena dependiendo del tiempo. Por supuesto, el esquema debe ser lo más breve posible, asumiendo que todo el correo está a tiempo.
Suma:
17 agentes deben enviar sus hallazgos por correo.
Si se interceptan 10 mensajes únicos, los agentes están listos.
El enemigo puede interceptar todos los mensajes en el centro postal dos veces.
El correo normalmente tarda un día en llegar, pero puede tardar más.
Ningún correo se pierde nunca (todo llega eventualmente).
El esquema debe funcionar independientemente del tiempo que tarde en llegar un mensaje en particular.
El esquema más corto (dado todo el correo a tiempo) gana.
Es posible que se envíen mensajes en blanco.
Respuestas
Encontré una solución usando
4 días, y esto es óptimo.
Esto funciona de la siguiente manera:
Dejar $A_0, \ldots, A_{16}$ ser los nombres de los agentes, y dejar $F_0, \ldots, F_{16}$denotar sus hallazgos.
Día 1:
$A_0$ envía $F_0$ a $A_1$
$A_4$ envía $F_4$ a $A_5$
$A_8$ envía $F_8$ a $A_9$
$A_{12}$ envía $F_{12}$ a $A_{13}$
$A_{16}$ envía $F_{16}$a todos los demás agentes (se envía exactamente el mismo mensaje a todos los agentes)
Día 2:
$A_1$ envía $F_0, F_1$ a $A_2$ (¡En un solo mensaje!)
$A_5$ envía $F_4, F_5$ a $A_6$
$A_9$ envía $F_8, F_9$ a $A_{10}$
$A_{13}$ envía $F_{12}, F_{13}$ a $A_{14}$
Día 3:
$A_2$ envía $F_0, F_1, F_2$ a $A_3$
$A_6$ envía $F_4, F_5, F_6$ a $A_7$
$A_{10}$ envía $F_8, F_9, F_{10}$ a $A_{11}$
$A_{14}$ envía $F_{12}, F_{13}, F_{14}$ a $A_{15}$
Día 4:
$A_3$ envía $F_0, F_1, F_2, F_3$ a todos los demás agentes (se envía exactamente el mismo mensaje a todos los agentes)
$A_7$ envía $F_4, F_5, F_6, F_7$ a todos los demás agentes
$A_{11}$ envía $F_8, F_9, F_{10}, F_{11}$ a todos los demás agentes
$A_{15}$ envía $F_{12}, F_{13}, F_{14}, F_{15}$a todos los demás agentes ¡
Y ahora todos los agentes han recibido todos los mensajes!
En el caso de que un mensaje se retrase, el agente que debe recibir este mensaje solo espera con el envío del siguiente mensaje hasta que se haya recibido el mensaje anterior.
La razón por la que el enemigo no puede interceptar 10 mensajes diferentes:
Tenga en cuenta que, en cualquier momento, hay como máximo 1 mensaje de $A_0$ a $A_3$ en la oficina de correos, como máximo 1 mensaje de $A_4$ a $A_7$, como máximo 1 mensaje de $A_8$ a $A_{11}$, como máximo 1 mensaje de $A_{12}$ a $A_{15}$ y posiblemente este el mensaje enviado por $A_{16}$. Entonces, hay como máximo 5 mensajes diferentes en la oficina de correos en cualquier momento, y si hay 5, entonces uno de ellos es el$A_{16}$. Esto implica que el gobierno puede interceptar como máximo 9 mensajes diferentes.
Además, este número de días es óptimo debido al siguiente argumento:
Dejar $M_i$ denotar el primer mensaje que contiene $F_i$ para cualquier $0 \leq i \leq 16$. Yo digo que si$i \neq j$, luego $M_i \neq M_j$: Supongamos sin pérdida de generalidad que la primera vez que $M_i$ se envía antes o el mismo día que la primera vez $M_j$se ha enviado. Ahora$M_i$ es enviado por $A_i$, quien no puede saber $F_j$ en el momento del envío, así que $M_i$ no contiene $F_j$, tiempo $M_j$lo hace.
Asi que al menos$17$ se deben enviar diferentes mensajes, ahora es fácil ver que estos no se pueden enviar en solo 3 días sin que haya dos días con un total de 10 mensajes diferentes en la oficina de correos.