Spie in Puzzlevania
Quello che sto per dirti non lascia questa stanza. Nell'ultimo anno, siamo cresciuti preoccupati per gli eventi nella nazione di Puzzlevania. Riteniamo che un grave attacco possa essere imminente. Tuttavia, il generale rifiuta di agire senza prove più concrete di una minaccia. A tal fine, ci stiamo preparando a inviare 16 spie e un capo dello spionaggio a Puzzlevania per ulteriori ricognizioni e valutazioni delle minacce. Ma c'è un problema.
Ogni agente deve condividere le proprie scoperte con gli altri 16 per assicurarsi che tutti possano seguire il piano di emergenza appropriato. Il nostro personale ha sviluppato un codice tale che qualsiasi messaggio appaia innocuo (e non incomprensibile) a un normale osservatore. Sfortunatamente, sono appena stato informato che Puzzlevania ha un nuovo dispositivo che sarà in grado di decifrare il nostro codice fornito solo 10 campioni unici.
L'invio di comunicazioni elettroniche è troppo rischioso dato questo dispositivo. La nostra unica speranza è fare affidamento sul tradizionale sistema di posta di Puzzlevania. La posta viene normalmente ritirata in un giorno, rimane nel centro postale durante la notte, quindi consegnata il giorno successivo (Puzzlevania non è così grande, quindi solo un centro postale). Tuttavia, a volte la posta rimane più notti, ma alla fine tutta la posta viene consegnata.
Gli ispettori del governo possono presentarsi di notte con il dispositivo di violazione del codice e fargli scansionare ogni pezzo di posta al centro. Quindi richiudono perfettamente tutta la posta e se ne vanno. Fortunatamente, altre fonti indicano di avere solo il budget per altre due ispezioni quest'anno e l'antica usanza proibisce la ricerca della posta inviata mentre non hanno budget (anche se ne ricevono di più in seguito).
Ho bisogno che tu elabori uno schema per assicurarti che tutti gli agenti possano inviare le loro scoperte agli altri senza che Puzzlevania infranga il codice. Puoi presumere che lo spymaster inizi qualsiasi catena basandosi sul tempismo. Ovviamente, lo schema dovrebbe essere il più breve possibile supponendo che tutta la posta sia puntuale.
Somma:
17 agenti devono inviare i risultati tramite posta.
Se vengono intercettati 10 messaggi univoci, gli agenti vengono avvisati.
Il nemico può intercettare due volte tutti i messaggi nel centro postale.
La posta normalmente impiega un giorno per arrivare, ma potrebbe essere necessario più tempo.
Nessuna posta va mai persa (alla fine arriva tutta).
Lo schema deve funzionare indipendentemente da quanto tempo impiega un particolare messaggio per arrivare.
Lo schema più breve (data tutta la posta in tempo) vince.
Possono essere inviati messaggi vuoti.
Risposte
Ho trovato una soluzione usando
4 giorni e questo è ottimale.
Funziona come segue:
Permettere $A_0, \ldots, A_{16}$ siano i nomi degli agenti e lascia $F_0, \ldots, F_{16}$denotano le loro scoperte.
Giorno 1:
$A_0$ invia $F_0$ per $A_1$
$A_4$ invia $F_4$ per $A_5$
$A_8$ invia $F_8$ per $A_9$
$A_{12}$ invia $F_{12}$ per $A_{13}$
$A_{16}$ invia $F_{16}$a tutti gli altri agenti (esattamente lo stesso messaggio viene inviato a tutti gli agenti)
Giorno 2:
$A_1$ invia $F_0, F_1$ per $A_2$ (In un unico messaggio!)
$A_5$ invia $F_4, F_5$ per $A_6$
$A_9$ invia $F_8, F_9$ per $A_{10}$
$A_{13}$ invia $F_{12}, F_{13}$ per $A_{14}$
3 ° giorno:
$A_2$ invia $F_0, F_1, F_2$ per $A_3$
$A_6$ invia $F_4, F_5, F_6$ per $A_7$
$A_{10}$ invia $F_8, F_9, F_{10}$ per $A_{11}$
$A_{14}$ invia $F_{12}, F_{13}, F_{14}$ per $A_{15}$
4 ° giorno:
$A_3$ invia $F_0, F_1, F_2, F_3$ a tutti gli altri agenti (esattamente lo stesso messaggio viene inviato a tutti gli agenti)
$A_7$ invia $F_4, F_5, F_6, F_7$ a tutti gli altri agenti
$A_{11}$ invia $F_8, F_9, F_{10}, F_{11}$ a tutti gli altri agenti
$A_{15}$ invia $F_{12}, F_{13}, F_{14}, F_{15}$a tutti gli altri agenti
E ora ogni agente ha ricevuto tutti i messaggi!
Nel caso in cui un messaggio venga ritardato, l'agente che dovrebbe ricevere questo messaggio attende con l'invio del messaggio successivo fino a quando non viene ricevuto il messaggio precedente.
Il motivo per cui il nemico non può intercettare 10 messaggi diversi:
Tieni presente che in qualsiasi momento è presente al massimo 1 messaggio da $A_0$ per $A_3$ all'ufficio postale, al massimo 1 messaggio da $A_4$ per $A_7$, al massimo 1 messaggio da $A_8$ per $A_{11}$, al massimo 1 messaggio da $A_{12}$ per $A_{15}$ e forse c'è il messaggio inviato da $A_{16}$. Quindi ci sono al massimo 5 messaggi diversi all'ufficio postale in qualsiasi momento, e se ce ne sono 5, uno di questi è il messaggio da$A_{16}$. Ciò implica che il governo può intercettare al massimo 9 messaggi diversi.
Inoltre, questo numero di giorni è ottimale a causa del seguente argomento:
Permettere $M_i$ denota il primo messaggio che contiene $F_i$ per ogni $0 \leq i \leq 16$. Affermo che se$i \neq j$, poi $M_i \neq M_j$: Supponiamo senza perdita di generalità che la prima volta $M_i$ viene inviato prima o lo stesso giorno della prima volta $M_j$è inviato. Adesso$M_i$ viene inviato da $A_i$, che non può sapere $F_j$ al momento dell'invio, quindi $M_i$ non contiene $F_j$, mentre $M_j$fa.
Almeno così$17$ devono essere inviati messaggi diversi, ora è facile vedere che questi non possono essere inviati in soli 3 giorni senza che ci siano due giorni con un totale di 10 messaggi diversi all'ufficio postale.