Puzzlevania의 스파이

Question

내가 말하려는 것은이 방을 떠나지 않습니다. 지난 1 년 동안 우리는 Puzzlevania 국가에서 발생하는 사건에 대해 걱정했습니다. 우리는 중대한 공격이 임박 할 것이라고 믿습니다. 그러나 장군은 위협에 대한 더 구체적인 증거없이 행동을 거부합니다. 이를 위해 추가 정찰 및 위협 평가를 위해 16 명의 스파이와 1 명의 스파이 마스터를 Puzzlevania에 파견 할 준비를하고 있습니다. 그러나 문제가 있습니다.

각 에이전트는 모든 사람이 적절한 비상 계획을 따를 수 있도록 다른 16 개와 자신의 결과를 공유해야합니다. 우리 직원들은 모든 메시지가 평범한 관찰자에게 무해하고 무의미하게 보이도록 코드를 개발했습니다. 불행히도, 저는 Puzzlevania가 10 개의 고유 한 샘플 만 제공하는 코드를 해독 할 수있는 새로운 장치를 가지고 있다는 소식을 받았습니다.

이 장치를 고려할 때 전자 통신을 보내는 것은 너무 위험합니다. 우리의 유일한 희망은 Puzzlevania의 전통적인 메일 시스템에 의존하는 것입니다. 우편물은 일반적으로 하루에 수거되어 하룻밤 사이에 우편 센터에 머무르고 다음 날 배달됩니다 (Puzzlevania는 그다지 크지 않으므로 우편 센터는 하나뿐입니다). 그러나 때로는 메일이 여러 날 동안 머 무르지 만 결국 모든 메일이 배달됩니다.

정부 조사관은 암호 해독 장치를 가지고 밤에 나타나 중앙에있는 모든 우편물을 검사하도록 할 수 있습니다. 그런 다음 모든 우편물을 완벽하게 다시 봉인하고 떠납니다. 다행히도 다른 소식통은 올해 두 번의 추가 검사에 대한 예산 만 보유하고 있으며 고대 관습에서는 예산이없는 동안 보낸 메일 검색을 금지하고 있습니다 (나중에 더 많이 확보하더라도).

모든 요원이 Puzzlevania가 코드를 깨뜨리지 않고 다른 사람에게 결과물을 보낼 수 있도록 계획을 세워야합니다. 스파이 마스터가 타이밍에 따라 모든 체인을 시작한다고 가정 할 수 있습니다. 물론 모든 메일이 정시에 도착한다고 가정 할 때 계획은 최대한 짧아야합니다.

요약:

17 명의 상담원이 결과를 우편으로 보내야합니다.

10 개의 고유 메시지를 가로 채면 에이전트가 알림을받습니다.

적군은 우편 센터의 모든 메시지를 두 번 가로 챌 수 있습니다.

우편물은 일반적으로 도착하는 데 하루가 걸리지 만 더 오래 걸릴 수 있습니다.

메일이 손실되지 않습니다 (모든 메일이 결국 도착합니다).

이 체계는 특정 메시지가 도착하는 데 걸리는 시간에 관계없이 작동해야합니다.

가장 짧은 계획 (모든 메일이 정시에 제공됨)이 이깁니다.

빈 메시지가 전송 될 수 있습니다.

Answer 1

나는 사용하는 해결책을 찾았다.

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 개의 서로 다른 메시지를 가로 챌 수 있음을 의미합니다.

또한이 날짜 수는 다음과 같은 인수로 인해 최적입니다.

허락하다 $M_i$ 포함하는 첫 번째 메시지를 나타냅니다. $F_i$ 어떠한 것도 $0 \leq i \leq 16$. 나는 주장한다$i \neq j$, 다음 $M_i \neq M_j$: 일반성을 잃지 않고 처음으로 $M_i$ 전송이 처음과 같은 날 또는 그 이전 일 경우 $M_j$보냈다. 지금$M_i$ 보낸 사람 $A_i$, 모르는 사람 $F_j$ 보낼 때 $M_i$ 포함되어 있지 않다 $F_j$, 동안 $M_j$않습니다.

그래서 적어도$17$ 서로 다른 메시지를 보내야합니다. 이제 우체국에 총 10 개의 다른 메시지가있는 이틀이 없으면 3 일만에 보낼 수 없다는 것을 쉽게 알 수 있습니다.