Mata-mata di Puzzlevania

Question

Apa yang akan saya katakan kepada Anda tidak meninggalkan ruangan ini. Selama setahun terakhir, kami semakin prihatin dengan kejadian di negara Puzzlevania. Kami yakin serangan besar mungkin akan segera terjadi. Namun, sang jenderal menolak untuk bertindak tanpa bukti ancaman yang lebih konkret. Untuk itu, kami bersiap untuk mengirim 16 mata-mata dan satu kepala intel ke Puzzlevania untuk pengintaian lebih lanjut dan penilaian ancaman. Tapi, ada tangkapan.

Setiap agen perlu membagikan temuan mereka dengan 16 agen lainnya untuk memastikan semua orang dapat mengikuti rencana darurat yang tepat. Orang-orang kami telah mengembangkan kode sedemikian rupa sehingga pesan apa pun tampak tidak berbahaya (dan tidak nonsens) bagi pengamat biasa. Sayangnya, saya baru saja diberi tahu bahwa Puzzlevania memiliki perangkat baru yang dapat memecahkan kode kami dengan hanya menyediakan 10 sampel unik.

Mengirim komunikasi elektronik terlalu berisiko mengingat perangkat ini. Satu-satunya harapan kami adalah mengandalkan sistem surat tradisional Puzzlevania. Biasanya surat diambil pada satu hari, tinggal di pusat pos semalaman, kemudian dikirim pada hari berikutnya (Puzzlevania tidak terlalu besar, jadi hanya satu pusat pos). Namun, terkadang email tetap beberapa malam, tetapi semua email akhirnya terkirim.

Inspektur pemerintah mungkin muncul di malam hari dengan perangkat pemecah kode dan memintanya memindai setiap bagian surat di tengah. Mereka kemudian dengan sempurna menutup kembali semua surat dan pergi. Untungnya, sumber lain menunjukkan bahwa mereka hanya memiliki anggaran untuk dua inspeksi lagi tahun ini, dan kebiasaan kuno melarang pencarian email yang dikirim saat mereka tidak memiliki anggaran (bahkan jika mereka mendapatkan lebih banyak kemudian).

Saya ingin Anda membuat skema untuk memastikan semua agen dapat mengirimkan temuan mereka kepada yang lain tanpa Puzzlevania melanggar kodenya. Anda dapat berasumsi bahwa kepala intel memulai rantai apa pun dengan mengandalkan waktu. Tentu saja, skema harus dibuat sesingkat mungkin dengan asumsi semua email tepat waktu.

Penjumlahan:

17 agen perlu mengirimkan temuan mereka melalui surat.

Jika 10 pesan unik dicegat, agen akan bersulang.

Musuh dapat mencegat semua pesan di pusat pos dua kali.

Mail biasanya membutuhkan satu hari untuk sampai, tapi bisa lebih lama.

Tidak ada email yang hilang (semuanya tiba pada akhirnya).

Skema harus berfungsi terlepas dari berapa lama pesan tertentu sampai.

Skema terpendek (semua email tepat waktu) menang.

Pesan kosong mungkin dikirim.

Answer 1

Saya menemukan solusi menggunakan

4 hari, dan ini optimal.

Ini bekerja sebagai berikut:

Membiarkan $A_0, \ldots, A_{16}$ menjadi nama agen, dan biarkan $F_0, \ldots, F_{16}$menunjukkan temuan mereka.

Hari 1:
$A_0$ mengirim $F_0$ untuk $A_1$
$A_4$ mengirim $F_4$ untuk $A_5$
$A_8$ mengirim $F_8$ untuk $A_9$
$A_{12}$ mengirim $F_{12}$ untuk $A_{13}$
$A_{16}$ mengirim $F_{16}$ke semua agen lain (pesan yang persis sama dikirim ke setiap agen)

Hari 2:
$A_1$ mengirim $F_0, F_1$ untuk $A_2$ (Dalam satu pesan!)
$A_5$ mengirim $F_4, F_5$ untuk $A_6$
$A_9$ mengirim $F_8, F_9$ untuk $A_{10}$
$A_{13}$ mengirim $F_{12}, F_{13}$ untuk $A_{14}$

Hari ke-3:
$A_2$ mengirim $F_0, F_1, F_2$ untuk $A_3$
$A_6$ mengirim $F_4, F_5, F_6$ untuk $A_7$
$A_{10}$ mengirim $F_8, F_9, F_{10}$ untuk $A_{11}$
$A_{14}$ mengirim $F_{12}, F_{13}, F_{14}$ untuk $A_{15}$

Hari 4:
$A_3$ mengirim $F_0, F_1, F_2, F_3$ ke semua agen lain (pesan yang persis sama dikirim ke setiap agen)
$A_7$ mengirim $F_4, F_5, F_6, F_7$ kepada semua agen lainnya
$A_{11}$ mengirim $F_8, F_9, F_{10}, F_{11}$ kepada semua agen lainnya
$A_{15}$ mengirim $F_{12}, F_{13}, F_{14}, F_{15}$ke semua agen lain
Dan sekarang setiap agen telah menerima semua pesan!

Dalam kasus di mana pesan tertunda, agen yang seharusnya menerima pesan ini hanya menunggu dengan mengirimkan pesan mereka berikutnya sampai pesan sebelumnya telah diterima.

Alasan mengapa musuh tidak dapat mencegat 10 pesan berbeda:

Perhatikan bahwa setiap saat, paling banyak ada 1 pesan dari $A_0$ untuk $A_3$ di kantor pos, maksimal 1 pesan dari $A_4$ untuk $A_7$, maksimal 1 pesan dari $A_8$ untuk $A_{11}$, maksimal 1 pesan dari $A_{12}$ untuk $A_{15}$ dan mungkin ada pesan yang dikirim oleh $A_{16}$. Jadi paling banyak ada 5 pesan berbeda di kantor pos setiap saat, dan jika ada 5, maka salah satunya adalah pesan dari$A_{16}$. Artinya, pemerintah dapat menyadap paling banyak 9 pesan berbeda.

Selain itu, jumlah hari ini optimal karena argumen berikut:

Membiarkan $M_i$ menunjukkan pesan pertama yang berisi $F_i$ untuk apapun $0 \leq i \leq 16$. Saya mengklaim bahwa jika$i \neq j$, kemudian $M_i \neq M_j$: Misalkan tanpa kehilangan keumuman bahwa pertama kali itu $M_i$ dikirim sebelum atau pada hari yang sama dengan pertama kali $M_j$terkirim. Sekarang$M_i$ dikirim oleh $A_i$, siapa yang tidak tahu $F_j$ pada saat pengiriman, jadi $M_i$ tidak mengandung $F_j$, sementara $M_j$tidak.

Setidaknya$17$ pesan berbeda harus dikirim, sekarang mudah dilihat bahwa pesan ini tidak dapat dikirim hanya dalam 3 hari tanpa ada dua hari dengan total 10 pesan berbeda di kantor pos.