Espiões em Puzzlevania
O que estou prestes a dizer não sai desta sala. No ano passado, ficamos preocupados com as ocorrências na nação de Puzzlevania. Acreditamos que um grande ataque pode ser iminente. No entanto, o general se recusa a agir sem evidências mais concretas de uma ameaça. Para esse fim, estamos nos preparando para enviar 16 espiões e um espião mestre para Puzzlevania para posterior reconhecimento e avaliação de ameaças. Mas, há um problema.
Cada agente precisa compartilhar suas descobertas com os outros 16 para garantir que todos possam seguir o plano de contingência adequado. Nosso pessoal desenvolveu um código para que qualquer mensagem pareça inofensiva (e não algo sem sentido) para um observador comum. Infelizmente, acabei de ser informado que Puzzlevania tem um novo dispositivo que será capaz de quebrar nosso código, desde que apenas 10 amostras únicas.
O envio de comunicações eletrônicas é muito arriscado devido a este dispositivo. Nossa única esperança é confiar no sistema de correio tradicional da Puzzlevania. O correio é normalmente recolhido num dia, permanece no centro postal durante a noite e entregue no seguinte (Puzzlevania não é tão grande, portanto, apenas um centro postal). No entanto, às vezes o correio permanece várias noites, mas todo o correio eventualmente é entregue.
Os inspetores do governo podem aparecer à noite com o dispositivo de quebra de código e fazer com que ele escaneie todas as correspondências no centro. Eles então fecham perfeitamente todas as correspondências e vão embora. Felizmente, outras fontes indicam que eles só têm orçamento para mais duas inspeções este ano, e o costume antigo proíbe a busca de correspondências enviadas enquanto eles não têm orçamento (mesmo que recebam mais depois).
Preciso que você crie um esquema para garantir que todos os agentes possam enviar suas descobertas para os outros sem que Puzzlevania decifre o código. Você pode assumir que o espião mestre inicia qualquer cadeia dependendo do tempo. Obviamente, o esquema deve ser o mais curto possível, assumindo que todas as correspondências estão no prazo.
Soma:
17 agentes precisam enviar suas descobertas por correio.
Se 10 mensagens exclusivas forem interceptadas, os agentes estarão prontos.
O inimigo pode interceptar todas as mensagens no centro postal duas vezes.
Normalmente, o correio demora um dia a chegar, mas pode demorar mais.
Nenhum e-mail é perdido (tudo chega eventualmente).
O esquema precisa funcionar independentemente de quanto tempo uma mensagem em particular leva para chegar.
O esquema mais curto (com todos os emails dentro do prazo) ganha.
Mensagens em branco podem ser enviadas.
Respostas
Eu encontrei uma solução usando
4 dias, e isso é o ideal.
Isso funciona da seguinte maneira:
Deixar $A_0, \ldots, A_{16}$ sejam os nomes dos agentes, e deixe $F_0, \ldots, F_{16}$denotam suas descobertas.
Dia 1:
$A_0$ envia $F_0$ para $A_1$
$A_4$ envia $F_4$ para $A_5$
$A_8$ envia $F_8$ para $A_9$
$A_{12}$ envia $F_{12}$ para $A_{13}$
$A_{16}$ envia $F_{16}$para todos os outros agentes (exatamente a mesma mensagem é enviada para todos os agentes)
Dia 2:
$A_1$ envia $F_0, F_1$ para $A_2$ (Em uma única mensagem!)
$A_5$ envia $F_4, F_5$ para $A_6$
$A_9$ envia $F_8, F_9$ para $A_{10}$
$A_{13}$ envia $F_{12}, F_{13}$ para $A_{14}$
Dia 3:
$A_2$ envia $F_0, F_1, F_2$ para $A_3$
$A_6$ envia $F_4, F_5, F_6$ para $A_7$
$A_{10}$ envia $F_8, F_9, F_{10}$ para $A_{11}$
$A_{14}$ envia $F_{12}, F_{13}, F_{14}$ para $A_{15}$
4º dia:
$A_3$ envia $F_0, F_1, F_2, F_3$ para todos os outros agentes (exatamente a mesma mensagem é enviada para todos os agentes)
$A_7$ envia $F_4, F_5, F_6, F_7$ para todos os outros agentes
$A_{11}$ envia $F_8, F_9, F_{10}, F_{11}$ para todos os outros agentes
$A_{15}$ envia $F_{12}, F_{13}, F_{14}, F_{15}$para todos os outros agentes
E agora todos os agentes receberam todas as mensagens!
No caso de atraso de uma mensagem, o agente que deve receber esta mensagem apenas aguarda com o envio da próxima mensagem até que a mensagem anterior seja recebida.
A razão pela qual o inimigo não consegue interceptar 10 mensagens diferentes:
Observe que, a qualquer momento, há no máximo 1 mensagem de $A_0$ para $A_3$ nos correios, no máximo 1 mensagem de $A_4$ para $A_7$, no máximo 1 mensagem de $A_8$ para $A_{11}$, no máximo 1 mensagem de $A_{12}$ para $A_{15}$ e possivelmente há a mensagem enviada por $A_{16}$. Portanto, há no máximo 5 mensagens diferentes nos correios a qualquer momento e, se houver 5, uma delas é a mensagem de$A_{16}$. Isso significa que o governo pode interceptar no máximo 9 mensagens diferentes.
Além disso, esse número de dias é ideal devido ao seguinte argumento:
Deixar $M_i$ denotam a primeira mensagem que contém $F_i$ para qualquer $0 \leq i \leq 16$. Eu reivindico que se$i \neq j$, então $M_i \neq M_j$: Suponha, sem perda de generalidade, que a primeira vez que $M_i$ é enviado antes ou no mesmo dia da primeira vez $M_j$é enviado. Agora$M_i$ é enviado por $A_i$, quem não pode saber $F_j$ na hora do envio, então $M_i$ não contém $F_j$, enquanto $M_j$faz.
Então pelo menos$17$ têm de ser enviadas mensagens diferentes, agora é fácil perceber que não se podem enviar em apenas 3 dias sem que haja dois dias com um total de 10 mensagens diferentes nos correios.