Gián điệp trong Puzzlevania

Question

Những gì tôi sắp nói với bạn đừng rời khỏi căn phòng này. Trong năm qua, chúng tôi ngày càng lo ngại về những sự kiện xảy ra ở quốc gia Puzzlevania. Chúng tôi tin rằng một cuộc tấn công lớn có thể sắp xảy ra. Tuy nhiên, vị tướng này từ chối hành động mà không có bằng chứng cụ thể hơn về mối đe dọa. Để đạt được mục tiêu đó, chúng tôi đang chuẩn bị cử 16 điệp viên và một người quay phim tới Puzzlevania để trinh sát thêm và đánh giá mối đe dọa. Nhưng, có một cơ hội.

Mỗi nhân viên cần chia sẻ những phát hiện của họ với 16 người khác để đảm bảo mọi người có thể tuân theo kế hoạch dự phòng thích hợp. Người của chúng tôi đã phát triển một mã sao cho bất kỳ thông điệp nào cũng có vẻ vô thưởng vô phạt (và không vô nghĩa) đối với một người quan sát bình thường. Thật không may, tôi vừa được thông báo rằng Puzzlevania có một thiết bị mới có thể bẻ khóa mã của chúng tôi với chỉ 10 mẫu duy nhất.

Gửi thông tin liên lạc điện tử là quá nhiều rủi ro đối với thiết bị này. Hy vọng duy nhất của chúng tôi là dựa vào hệ thống thư truyền thống của Puzzlevania. Thư thường được nhận vào một ngày, ở lại trung tâm bưu điện qua đêm, sau đó sẽ được giao vào ngày tiếp theo (Puzzlevania không lớn như vậy nên chỉ có một trung tâm bưu điện). Tuy nhiên, đôi khi thư ở lại nhiều đêm, nhưng cuối cùng tất cả thư đều được chuyển đi.

Thanh tra chính phủ có thể xuất hiện vào ban đêm với thiết bị bẻ mã và yêu cầu nó quét mọi mẩu thư trong trung tâm. Sau đó, họ hoàn toàn gửi lại tất cả thư và rời đi. May mắn thay, các nguồn khác cho biết họ chỉ có ngân sách cho hai lần kiểm tra nữa trong năm nay và phong tục cổ đại cấm tìm kiếm thư được gửi trong khi họ không có ngân sách (ngay cả khi họ nhận được nhiều hơn sau đó).

Tôi cần bạn nghĩ ra một kế hoạch để đảm bảo tất cả các đặc vụ có thể gửi phát hiện của họ cho những người khác mà không bị Puzzlevania phá mã. Bạn có thể cho rằng máy quay bắt đầu bất kỳ chuỗi nào dựa trên thời gian. Tất nhiên, lược đồ phải càng ngắn càng tốt với điều kiện là tất cả thư đều đúng giờ.

Tổng kết:

17 đặc vụ cần gửi phát hiện của họ qua thư.

Nếu 10 tin nhắn duy nhất bị chặn, các đại lý sẽ nâng cốc.

Kẻ thù có thể chặn tất cả các thư trong trung tâm bưu điện hai lần.

Thư thường mất một ngày để đến nơi, nhưng có thể lâu hơn.

Không có thư nào bị mất (cuối cùng tất cả đều đến).

Lược đồ cần phải hoạt động bất kể mất bao lâu để có bất kỳ thông báo cụ thể nào.

Lược đồ ngắn nhất (đưa ra tất cả thư đúng hạn) sẽ thắng.

Tin nhắn trống có thể được gửi.

Answer 1

Tôi đã tìm thấy một giải pháp bằng cách sử dụng

4 ngày, và điều này là tối ưu.

Điều này hoạt động như sau:

Để cho $A_0, \ldots, A_{16}$ là tên của các đại lý, và để $F_0, \ldots, F_{16}$biểu thị những phát hiện của họ.

1 ngày:
$A_0$ gửi $F_0$ đến $A_1$
$A_4$ gửi $F_4$ đến $A_5$
$A_8$ gửi $F_8$ đến $A_9$
$A_{12}$ gửi $F_{12}$ đến $A_{13}$
$A_{16}$ gửi $F_{16}$cho tất cả các đại lý khác (chính xác cùng một thông báo được gửi đến mọi đại lý)

Ngày 2:
$A_1$ gửi $F_0, F_1$ đến $A_2$ (Trong một tin nhắn!)
$A_5$ gửi $F_4, F_5$ đến $A_6$
$A_9$ gửi $F_8, F_9$ đến $A_{10}$
$A_{13}$ gửi $F_{12}, F_{13}$ đến $A_{14}$

Ngày 3:
$A_2$ gửi $F_0, F_1, F_2$ đến $A_3$
$A_6$ gửi $F_4, F_5, F_6$ đến $A_7$
$A_{10}$ gửi $F_8, F_9, F_{10}$ đến $A_{11}$
$A_{14}$ gửi $F_{12}, F_{13}, F_{14}$ đến $A_{15}$

Ngày 4:
$A_3$ gửi $F_0, F_1, F_2, F_3$ cho tất cả các đại lý khác (chính xác cùng một thông báo được gửi đến mọi đại lý)
$A_7$ gửi $F_4, F_5, F_6, F_7$ cho tất cả các đại lý khác
$A_{11}$ gửi $F_8, F_9, F_{10}, F_{11}$ cho tất cả các đại lý khác
$A_{15}$ gửi $F_{12}, F_{13}, F_{14}, F_{15}$cho tất cả các đại lý khác
Và bây giờ mỗi đại lý đã nhận được tất cả các tin nhắn!

Trong trường hợp một tin nhắn bị trì hoãn, nhân viên sẽ nhận được tin nhắn này chỉ cần đợi gửi tin nhắn tiếp theo của họ cho đến khi nhận được tin nhắn trước đó.

Lý do tại sao đối phương không thể chặn được 10 tin nhắn khác nhau:

Lưu ý rằng tại bất kỳ thời điểm nào, có nhiều nhất 1 tin nhắn từ $A_0$ đến $A_3$ tại bưu điện, nhiều nhất 1 tin nhắn từ $A_4$ đến $A_7$, nhiều nhất 1 tin nhắn từ $A_8$ đến $A_{11}$, nhiều nhất 1 tin nhắn từ $A_{12}$ đến $A_{15}$ và có thể có tin nhắn được gửi bởi $A_{16}$. Vì vậy, có nhiều nhất 5 tin nhắn khác nhau tại bưu điện vào bất kỳ lúc nào và nếu có 5 tin nhắn thì một trong số đó là tin nhắn từ$A_{16}$. Điều này ngụ ý rằng chính phủ có thể chặn tối đa 9 thông điệp khác nhau.

Hơn nữa, số ngày này là tối ưu vì đối số sau:

Để cho $M_i$ biểu thị tin nhắn đầu tiên chứa $F_i$ bất cứ gì $0 \leq i \leq 16$. Tôi khẳng định rằng nếu$i \neq j$, sau đó $M_i \neq M_j$: Giả sử không mất tính tổng quát rằng lần đầu tiên $M_i$ được gửi trước hoặc cùng ngày với lần đầu tiên $M_j$đã được gửi. Hiện nay$M_i$ được gửi bởi $A_i$, ai không thể biết $F_j$ tại thời điểm gửi, vì vậy $M_i$ không chứa $F_j$, trong khi $M_j$làm.

Vì vậy, ít nhất$17$ các tin nhắn khác nhau phải được gửi đi, hiện nay có thể dễ dàng nhận thấy rằng không thể chỉ gửi trong 3 ngày mà không có hai ngày với tổng số 10 tin nhắn khác nhau tại bưu điện.