Szpiedzy w Puzzlevanii

Question

To, co ci powiem, nie opuszcza tego pokoju. Przez ostatni rok byliśmy coraz bardziej zaniepokojeni wydarzeniami w kraju Puzzlevania. Uważamy, że poważny atak może być nieuchronny. Jednak generał odmawia działania bez bardziej konkretnych dowodów zagrożenia. W tym celu przygotowujemy się do wysłania 16 szpiegów i jednego mistrza szpiegów do Puzzlevanii w celu dalszego rozpoznania i oceny zagrożenia. Ale jest haczyk.

Każdy agent musi podzielić się swoimi spostrzeżeniami z pozostałymi 16, aby upewnić się, że każdy może postępować zgodnie z odpowiednim planem awaryjnym. Nasi ludzie opracowali kod w taki sposób, że każda wiadomość wydaje się nieszkodliwa (i bez bełkotu) dla zwykłego obserwatora. Niestety, właśnie zostałem poinformowany, że Puzzlevania ma nowe urządzenie, które będzie w stanie złamać nasz kod, pod warunkiem, że tylko 10 unikalnych próbek.

Wysyłanie wiadomości elektronicznych jest zbyt ryzykowne, biorąc pod uwagę to urządzenie. Naszą jedyną nadzieją jest poleganie na tradycyjnym systemie pocztowym Puzzlevania. Przesyłka jest zwykle odbierana jednego dnia, pozostaje w centrum pocztowym przez noc, a następnie dostarczana następnego dnia (Puzzlevania nie jest tak duża, więc tylko jedno centrum pocztowe). Czasami jednak poczta pozostaje na wiele nocy, ale ostatecznie cała poczta jest dostarczana.

Inspektorzy rządowi mogą pojawić się w nocy z urządzeniem do łamania kodów i zlecić skanowanie każdej przesyłki w centrum. Następnie doskonale ponownie zamykają całą pocztę i wychodzą. Na szczęście inne źródła podają, że w tym roku mają budżet tylko na dwie dodatkowe inspekcje, a starożytny zwyczaj zabrania przeszukiwania poczty wysłanej bez budżetu (nawet jeśli później otrzyma więcej).

Chcę, żebyś wymyślił plan, który zapewni wszystkim agentom możliwość przesłania swoich ustaleń innym bez łamania kodu przez Puzzlevania. Możesz założyć, że mistrz szpiegów rozpoczyna łańcuchy zależne od czasu. Oczywiście schemat powinien być jak najkrótszy, zakładając, że cała poczta jest na czas.

Podsumowanie:

17 agentów musi przesłać swoje ustalenia pocztą.

Jeśli przechwyconych zostanie 10 unikalnych wiadomości, agenci się wznoszą.

Wróg może dwukrotnie przechwycić wszystkie wiadomości w centrum pocztowym.

Poczta zwykle dociera w ciągu jednego dnia, ale może to potrwać dłużej.

Żadna poczta nie jest nigdy tracona (wszystko w końcu dociera).

Schemat musi działać niezależnie od tego, ile czasu zajmie dotarcie do określonej wiadomości.

Najkrótszy schemat (otrzymując wszystkie wiadomości na czas) wygrywa.

Mogą zostać wysłane puste wiadomości.

Answer 1

Znalazłem rozwiązanie za pomocą

4 dni i to jest optymalne.

Działa to w następujący sposób:

Pozwolić $A_0, \ldots, A_{16}$ być nazwiskami agentów i niech $F_0, \ldots, F_{16}$oznaczają ich ustalenia.

Dzień 1:
$A_0$ wysyła $F_0$ do $A_1$
$A_4$ wysyła $F_4$ do $A_5$
$A_8$ wysyła $F_8$ do $A_9$
$A_{12}$ wysyła $F_{12}$ do $A_{13}$
$A_{16}$ wysyła $F_{16}$do wszystkich innych agentów (dokładnie ta sama wiadomość jest wysyłana do każdego agenta)

Dzień 2:
$A_1$ wysyła $F_0, F_1$ do $A_2$ (W jednej wiadomości!)
$A_5$ wysyła $F_4, F_5$ do $A_6$
$A_9$ wysyła $F_8, F_9$ do $A_{10}$
$A_{13}$ wysyła $F_{12}, F_{13}$ do $A_{14}$

Dzień 3:
$A_2$ wysyła $F_0, F_1, F_2$ do $A_3$
$A_6$ wysyła $F_4, F_5, F_6$ do $A_7$
$A_{10}$ wysyła $F_8, F_9, F_{10}$ do $A_{11}$
$A_{14}$ wysyła $F_{12}, F_{13}, F_{14}$ do $A_{15}$

4 dzień:
$A_3$ wysyła $F_0, F_1, F_2, F_3$ do wszystkich innych agentów (dokładnie ta sama wiadomość jest wysyłana do każdego agenta)
$A_7$ wysyła $F_4, F_5, F_6, F_7$ wszystkim innym agentom
$A_{11}$ wysyła $F_8, F_9, F_{10}, F_{11}$ wszystkim innym agentom
$A_{15}$ wysyła $F_{12}, F_{13}, F_{14}, F_{15}$do wszystkich innych agentów
A teraz każdy agent otrzymał wszystkie wiadomości!

W przypadku, gdy wiadomość jest opóźniona, agent, który powinien ją odebrać, po prostu czeka z wysłaniem kolejnej wiadomości, aż do odebrania poprzedniej wiadomości.

Powód, dla którego wróg nie może przechwycić 10 różnych wiadomości:

Zauważ, że w dowolnym momencie jest co najwyżej 1 wiadomość od $A_0$ do $A_3$ na poczcie, najwyżej 1 wiadomość od $A_4$ do $A_7$, maksymalnie 1 wiadomość od $A_8$ do $A_{11}$, maksymalnie 1 wiadomość od $A_{12}$ do $A_{15}$ i prawdopodobnie jest wiadomość wysłana przez $A_{16}$. Więc na poczcie jest co najwyżej 5 różnych wiadomości w dowolnym momencie, a jeśli jest ich 5, to jedna z nich jest wiadomością od$A_{16}$. Oznacza to, że rząd może przechwycić maksymalnie 9 różnych wiadomości.

Ponadto ta liczba dni jest optymalna ze względu na następujący argument:

Pozwolić $M_i$ oznacza pierwszą wiadomość, która zawiera $F_i$ dla każdego $0 \leq i \leq 16$. Twierdzę, że jeśli$i \neq j$, następnie $M_i \neq M_j$: Załóżmy bez utraty ogólności, że za pierwszym razem $M_i$ jest wysyłane przed lub w tym samym dniu co po raz pierwszy $M_j$jest wysłany. Teraz$M_i$ jest wysyłany przez $A_i$kto nie może wiedzieć $F_j$ w momencie nadania tzw $M_i$ nie zawiera $F_j$, podczas $M_j$robi.

A więc przynajmniej$17$ trzeba wysłać różne wiadomości, teraz łatwo zauważyć, że nie można ich wysłać w ciągu zaledwie 3 dni bez dwóch dni z łącznie 10 różnymi wiadomościami na poczcie.