Puzzlevania'daki Casuslar
Sana söyleyeceğim şey bu odadan çıkmıyor. Geçtiğimiz yıl, Puzzlevania ulusundaki olaylardan endişe duymaya başladık. Büyük bir saldırının yakın olabileceğine inanıyoruz. Bununla birlikte, general bir tehdide dair daha somut kanıtlar olmadan hareket etmeyi reddediyor. Bu amaçla, daha fazla keşif ve tehdit değerlendirmesi için Puzzlevania'ya 16 casus ve bir casus usta göndermeye hazırlanıyoruz. Ancak, bir sorun var.
Herkesin uygun acil durum planını takip edebilmesini sağlamak için her temsilcinin bulgularını diğer 16 ile paylaşması gerekir. Halkımız, herhangi bir mesajın sıradan bir gözlemciye zararsız (ve anlamsız) görünmesini sağlayacak bir kod geliştirdi. Ne yazık ki, Puzzlevania'nın yalnızca 10 benzersiz örnek sağladığımız kodumuzu kırabilecek yeni bir cihaza sahip olduğu konusunda bilgilendirildim.
Bu cihaz göz önüne alındığında elektronik iletişim göndermek çok risklidir. Tek umudumuz Puzzlevania'nın geleneksel posta sistemine güvenmektir. Posta normalde bir gün alınır, bir gece posta merkezinde kalır, ardından bir sonraki gün gönderilir (Puzzlevania o kadar büyük değildir, bu nedenle yalnızca bir posta merkezi). Bununla birlikte, bazen postalar birden çok gece kalır, ancak sonunda tüm postalar teslim edilir.
Hükümet müfettişleri, geceleri şifre kırma cihazıyla gelip merkezdeki her postayı taratabilir. Daha sonra tüm postaları mükemmel bir şekilde yeniden kapatırlar ve ayrılırlar. Neyse ki, diğer kaynaklar bu yıl yalnızca iki denetim için daha bütçeye sahip olduklarını ve eski gelenekler bütçeleri yokken gönderilen postaları aramayı yasakladığını belirtiyor (daha sonra daha fazlasını alsalar bile).
Tüm temsilcilerin bulgularını Puzzlevania'yı kodu kırmadan diğerlerine gönderebilmelerini sağlamak için bir plan tasarlamanıza ihtiyacım var. Casus yöneticisinin zamanlamaya bağlı olarak herhangi bir zincir başlattığını varsayabilirsiniz. Elbette, tüm postaların zamanında olduğu varsayılarak program mümkün olduğunca kısa olmalıdır.
Özet:
17 temsilcinin bulgularını posta yoluyla göndermesi gerekiyor.
10 benzersiz mesaj ele geçirilirse, ajanlar çaresizdir.
Düşman posta merkezindeki tüm mesajları iki kez kesebilir.
Postanın ulaşması normalde bir gün sürer ancak daha uzun sürebilir.
Hiçbir posta kaybolmaz (hepsi sonunda ulaşır).
Programın, belirli bir mesajın ulaşması ne kadar sürdüğüne bakılmaksızın çalışması gerekir.
En kısa şema (tüm postalar zamanında verilir) kazanır.
Boş mesajlar gönderilebilir.
Yanıtlar
Kullanarak bir çözüm buldum
4 gün ve bu en uygunudur.
Bu şu şekilde çalışır:
İzin Vermek $A_0, \ldots, A_{16}$ ajanların isimleri olsun ve $F_0, \ldots, F_{16}$bulgularını ifade eder.
1.gün:
$A_0$ gönderir $F_0$ -e $A_1$
$A_4$ gönderir $F_4$ -e $A_5$
$A_8$ gönderir $F_8$ -e $A_9$
$A_{12}$ gönderir $F_{12}$ -e $A_{13}$
$A_{16}$ gönderir $F_{16}$diğer tüm aracılara (her temsilciye tam olarak aynı mesaj gönderilir)
2. Gün:
$A_1$ gönderir $F_0, F_1$ -e $A_2$ (Tek bir mesajda!)
$A_5$ gönderir $F_4, F_5$ -e $A_6$
$A_9$ gönderir $F_8, F_9$ -e $A_{10}$
$A_{13}$ gönderir $F_{12}, F_{13}$ -e $A_{14}$
3 gün:
$A_2$ gönderir $F_0, F_1, F_2$ -e $A_3$
$A_6$ gönderir $F_4, F_5, F_6$ -e $A_7$
$A_{10}$ gönderir $F_8, F_9, F_{10}$ -e $A_{11}$
$A_{14}$ gönderir $F_{12}, F_{13}, F_{14}$ -e $A_{15}$
4. Gün:
$A_3$ gönderir $F_0, F_1, F_2, F_3$ diğer tüm aracılara (her temsilciye tam olarak aynı mesaj gönderilir)
$A_7$ gönderir $F_4, F_5, F_6, F_7$ diğer tüm ajanlara
$A_{11}$ gönderir $F_8, F_9, F_{10}, F_{11}$ diğer tüm ajanlara
$A_{15}$ gönderir $F_{12}, F_{13}, F_{14}, F_{15}$tüm diğer ajanlara
Ve şimdi her temsilci tüm mesajları aldı!
Bir mesajın gecikmesi durumunda, bu mesajı alması gereken temsilci, bir önceki mesaj alınana kadar bir sonraki mesajını göndermeyi bekler.
Düşmanın 10 farklı mesajı kesememesinin nedeni:
Herhangi bir anda, gelen en fazla 1 mesaj olduğunu unutmayın. $A_0$ -e $A_3$ postanede, gönderen en fazla 1 mesaj $A_4$ -e $A_7$, gönderen en fazla 1 mesaj $A_8$ -e $A_{11}$, en fazla 1 mesaj: $A_{12}$ -e $A_{15}$ ve muhtemelen tarafından gönderilen mesaj var $A_{16}$. Yani postanede herhangi bir zamanda en fazla 5 farklı mesaj var ve 5 tane varsa, bunlardan biri$A_{16}$. Bu, hükümetin en fazla 9 farklı mesajı yakalayabileceği anlamına gelir.
Ayrıca, aşağıdaki argüman nedeniyle bu gün sayısı optimaldir:
İzin Vermek $M_i$ içeren ilk mesajı gösterir $F_i$ herhangi $0 \leq i \leq 16$. İddia ediyorum eğer$i \neq j$, sonra $M_i \neq M_j$: Varsayalım ki genelliği kaybetmeden ilk seferinde $M_i$ gönderildiği günden önce veya ilk kez olduğu gün $M_j$gönderildi. Şimdi$M_i$ tarafından gönderildi $A_i$kim bilemez $F_j$ gönderirken, bu yüzden $M_i$ içermiyor $F_j$, süre $M_j$yapar.
En azından$17$ farklı mesajların gönderilmesi gerekiyor, artık postanede toplam 10 farklı mesajla iki gün olmadan bunların sadece 3 günde gönderilemeyeceğini görmek çok kolay.