สายลับใน Puzzlevania

Oct 24 2020

สิ่งที่ฉันกำลังจะบอกคุณอย่าออกจากห้องนี้ ในปีที่ผ่านมาเรามีความกังวลมากขึ้นจากเหตุการณ์ที่เกิดขึ้นในประเทศ Puzzlevania เราเชื่อว่าการโจมตีครั้งใหญ่อาจใกล้เข้ามา อย่างไรก็ตามคนทั่วไปปฏิเสธที่จะดำเนินการโดยไม่มีหลักฐานที่เป็นรูปธรรมมากขึ้นว่าเป็นภัยคุกคาม ด้วยเหตุนี้เรากำลังเตรียมที่จะส่งสายลับ 16 คนและผู้แพร่กระจายหนึ่งคนไปยัง Puzzlevania เพื่อทำการตรวจสอบและประเมินภัยคุกคามต่อไป แต่มีการจับ

ตัวแทนแต่ละคนจำเป็นต้องแบ่งปันสิ่งที่พบกับอีก 16 คนเพื่อให้แน่ใจว่าทุกคนสามารถปฏิบัติตามแผนฉุกเฉินที่เหมาะสมได้ บุคลากรของเราได้พัฒนารหัสเพื่อให้ข้อความใด ๆ ดูไม่มีพิษมีภัย (และไม่เป็นการพูดพล่อยๆ) ต่อผู้สังเกตการณ์ทั่วไป น่าเสียดายที่ฉันเพิ่งได้รับแจ้งว่า Puzzlevania มีอุปกรณ์ใหม่ซึ่งจะสามารถถอดรหัสรหัสของเราได้โดยมีตัวอย่างที่ไม่ซ้ำกันเพียง 10 ตัวอย่างเท่านั้น

การส่งการสื่อสารทางอิเล็กทรอนิกส์มีความเสี่ยงมากเกินไปสำหรับอุปกรณ์นี้ ความหวังเดียวของเราคือการใช้ระบบจดหมายแบบดั้งเดิมของ Puzzlevania โดยปกติแล้วจะมีการรับจดหมายในวันเดียวอยู่ที่ศูนย์ไปรษณีย์ข้ามคืนจากนั้นจัดส่งในวันถัดไป (Puzzlevania ไม่ได้ใหญ่ขนาดนั้นมีศูนย์ไปรษณีย์เพียงแห่งเดียว) อย่างไรก็ตามบางครั้งจดหมายจะอยู่หลายคืน แต่ในที่สุดจดหมายทั้งหมดก็ได้รับการจัดส่ง

เจ้าหน้าที่ตรวจสอบของรัฐบาลอาจปรากฏตัวในเวลากลางคืนพร้อมกับอุปกรณ์ทำลายรหัสและให้สแกนจดหมายทุกชิ้นที่อยู่ตรงกลาง จากนั้นพวกเขาปิดผนึกจดหมายทั้งหมดอย่างสมบูรณ์แบบและจากไป โชคดีที่แหล่งข้อมูลอื่นระบุว่าพวกเขามีงบประมาณสำหรับการตรวจสอบอีกสองครั้งในปีนี้และประเพณีโบราณห้ามไม่ให้ค้นหาจดหมายที่ส่งในขณะที่พวกเขาไม่มีงบประมาณ (แม้ว่าจะได้รับมากกว่านี้ในภายหลังก็ตาม)

ฉันต้องการให้คุณวางแผนเพื่อให้แน่ใจว่าตัวแทนทั้งหมดสามารถส่งสิ่งที่ค้นพบไปยังผู้อื่นได้โดยที่ Puzzlevania ไม่ทำลายรหัส คุณอาจสมมติว่า spymaster เริ่มต้นโซ่ใด ๆ โดยอาศัยเวลา แน่นอนว่าโครงการควรสั้นที่สุดเท่าที่จะเป็นไปได้โดยสมมติว่าจดหมายทั้งหมดตรงเวลา

สรุป:

ตัวแทน 17 คนจำเป็นต้องส่งสิ่งที่ค้นพบทางไปรษณีย์

หากข้อความที่ไม่ซ้ำกัน 10 ข้อความถูกสกัดกั้นตัวแทนจะถูกปิ้ง

ศัตรูอาจดักฟังข้อความทั้งหมดในศูนย์ไปรษณีย์สองครั้ง

โดยปกติจดหมายจะใช้เวลาถึงหนึ่งวัน แต่อาจใช้เวลานานกว่านั้น

ไม่มีจดหมายสูญหาย (ทุกอย่างก็มาถึงในที่สุด)

โครงร่างต้องใช้งานได้ไม่ว่าข้อความใด ๆ จะมาถึงนานแค่ไหนก็ตาม

โครงการที่สั้นที่สุด (ให้จดหมายตรงเวลาทั้งหมด) ชนะ

อาจมีการส่งข้อความเปล่า

คำตอบ

3 Reinier Oct 24 2020 at 18:16

ฉันพบวิธีแก้ปัญหาโดยใช้

4 วันและนี่คือสิ่งที่ดีที่สุด

ทำงานได้ดังนี้:

ปล่อย $A_0, \ldots, A_{16}$ เป็นชื่อของตัวแทนและปล่อยให้ $F_0, \ldots, F_{16}$แสดงถึงการค้นพบของพวกเขา

วันที่ 1:
$A_0$ ส่ง $F_0$ ถึง $A_1$
$A_4$ ส่ง $F_4$ ถึง $A_5$
$A_8$ ส่ง $F_8$ ถึง $A_9$
$A_{12}$ ส่ง $F_{12}$ ถึง $A_{13}$
$A_{16}$ ส่ง $F_{16}$ถึงตัวแทนอื่น ๆ ทั้งหมด (ส่งข้อความเดียวกันถึงตัวแทนทุกคน)

วันที่ 2:
$A_1$ ส่ง $F_0, F_1$ ถึง $A_2$ (ในข้อความเดียว!)
$A_5$ ส่ง $F_4, F_5$ ถึง $A_6$
$A_9$ ส่ง $F_8, F_9$ ถึง $A_{10}$
$A_{13}$ ส่ง $F_{12}, F_{13}$ ถึง $A_{14}$

วันที่ 3:
$A_2$ ส่ง $F_0, F_1, F_2$ ถึง $A_3$
$A_6$ ส่ง $F_4, F_5, F_6$ ถึง $A_7$
$A_{10}$ ส่ง $F_8, F_9, F_{10}$ ถึง $A_{11}$
$A_{14}$ ส่ง $F_{12}, F_{13}, F_{14}$ ถึง $A_{15}$

วันที่ 4:
$A_3$ ส่ง $F_0, F_1, F_2, F_3$ ถึงตัวแทนอื่น ๆ ทั้งหมด (ข้อความเดียวกันทุกประการจะถูกส่งไปยังตัวแทนทุกคน)
$A_7$ ส่ง $F_4, F_5, F_6, F_7$ ให้กับตัวแทนอื่น ๆ ทั้งหมด
$A_{11}$ ส่ง $F_8, F_9, F_{10}, F_{11}$ ให้กับตัวแทนอื่น ๆ ทั้งหมด
$A_{15}$ ส่ง $F_{12}, F_{13}, F_{14}, F_{15}$ถึงตัวแทนอื่น ๆ
และตอนนี้ตัวแทนทุกคนได้รับข้อความทั้งหมดแล้ว!

ในกรณีที่ข้อความล่าช้าตัวแทนที่ควรได้รับข้อความนี้เพียงแค่รอส่งข้อความถัดไปจนกว่าจะได้รับข้อความก่อนหน้านี้

สาเหตุที่ศัตรูไม่สามารถสกัดกั้น 10 ข้อความที่แตกต่างกัน:

โปรดทราบว่ามีข้อความมากที่สุด 1 ข้อความจากเมื่อใดก็ได้ $A_0$ ถึง $A_3$ ที่ไปรษณีย์มากสุด 1 ข้อความจาก $A_4$ ถึง $A_7$สูงสุด 1 ข้อความจาก $A_8$ ถึง $A_{11}$สูงสุด 1 ข้อความจาก $A_{12}$ ถึง $A_{15}$ และอาจมีข้อความที่ส่งมา $A_{16}$. ดังนั้นจึงมีข้อความที่แตกต่างกันมากที่สุด 5 ข้อความที่ที่ทำการไปรษณีย์ได้ตลอดเวลาและถ้ามี 5 ข้อความหนึ่งในนั้นคือข้อความจาก$A_{16}$. นี่หมายความว่ารัฐบาลสามารถดักฟังข้อความต่างๆได้สูงสุด 9 ข้อความ

นอกจากนี้จำนวนวันนี้เหมาะสมที่สุดเนื่องจากอาร์กิวเมนต์ต่อไปนี้: