3
$\begingroup$

What I am about to tell you doesn't leave this room. For the past year, we've grown concerned by occurrences in the nation of Puzzlevania. We believe a major attack may be imminent. However, the general refuses to act without more concrete evidence of a threat. To that end, we are preparing to dispatch 16 spies and one spymaster to Puzzlevania for further recon and threat assessment. But, there's a catch.

Each agent needs to share their findings with the other 16 to ensure everyone can follow the proper contingency plan. Our people have developed a code such that any message appears innocuous (and non-gibberish) to an ordinary observer. Unfortunately, I've just been informed that Puzzlevania has a new device which will be able to crack our code provided only 10 unique samples.

Sending electronic communications is far too risky given this device. Our only hope is relying on Puzzlevania's traditional mail system. The mail is normally picked up on one day, stays in the postal center overnight, then delivered the next (Puzzlevania isn't that large, so only one postal center). However, sometimes mail stays multiple nights, but all mail eventually gets delivered.

Government inspectors may show up at night with the codebreaking device and have it scan every piece of mail in the center. They then perfectly reseal all mail and leave. Fortunately, other sources indicate they only have the budget for two more inspections this year, and ancient custom prohibits searching mail sent while they have no budget (even if they get more later).

I need you to devise a scheme to ensure all agents can send their findings to the others without Puzzlevania breaking the code. You may assume the spymaster begins any chains relying on timing. Of course, the scheme should be as short as possible assuming all mail is on time.

Summation:

17 agents need to send their findings via mail.

If 10 unique messages are intercepted, the agents are toast.

The enemy may intercept all messages in the postal center twice.

Mail normally takes a day to arrive, but may take longer.

No mail is ever lost (it all arrives eventually).

The scheme needs to work regardless of how long any particular message takes to arrive.

Shortest scheme (given all mail on time) wins.

Blank messages may be sent.

$\endgroup$
  • $\begingroup$ Since we are still in the preparation phase, replace the coding scheme with 272 one-time pads, one for each required communication. Decorate with steganography (acrostics should suffice) if you need the messages to look non-gibberish. Done in one day. $\endgroup$ – Bass Oct 24 at 9:35
3
$\begingroup$

I found a solution using

4 days, and this is optimal.

This works as follows:

Let $A_0, \ldots, A_{16}$ be the names of the agents, and let $F_0, \ldots, F_{16}$ denote their findings.

Day 1:
$A_0$ sends $F_0$ to $A_1$
$A_4$ sends $F_4$ to $A_5$
$A_8$ sends $F_8$ to $A_9$
$A_{12}$ sends $F_{12}$ to $A_{13}$
$A_{16}$ sends $F_{16}$ to all other agents (exactly the same message is sent to every agent)

Day 2:
$A_1$ sends $F_0, F_1$ to $A_2$ (In a single message!)
$A_5$ sends $F_4, F_5$ to $A_6$
$A_9$ sends $F_8, F_9$ to $A_{10}$
$A_{13}$ sends $F_{12}, F_{13}$ to $A_{14}$

Day 3:
$A_2$ sends $F_0, F_1, F_2$ to $A_3$
$A_6$ sends $F_4, F_5, F_6$ to $A_7$
$A_{10}$ sends $F_8, F_9, F_{10}$ to $A_{11}$
$A_{14}$ sends $F_{12}, F_{13}, F_{14}$ to $A_{15}$

Day 4:
$A_3$ sends $F_0, F_1, F_2, F_3$ to all other agents (exactly the same message is sent to every agent)
$A_7$ sends $F_4, F_5, F_6, F_7$ to all other agents
$A_{11}$ sends $F_8, F_9, F_{10}, F_{11}$ to all other agents
$A_{15}$ sends $F_{12}, F_{13}, F_{14}, F_{15}$ to all other agents
And now every agent has received all messages!

In the case where a message is delayed, the agent who should receive this message just waits with sending their next message until the previous message has been received.

The reason why the enemy cannot intercept 10 different messages:

Note that at any moment, there is at most 1 message from $A_0$ to $A_3$ at the post office, at most 1 message from $A_4$ to $A_7$, at most 1 message from $A_8$ to $A_{11}$, at most 1 messages from $A_{12}$ to $A_{15}$ and possibly there is the message sent by $A_{16}$. So there are at most 5 different messages at the post office at any time, and if there are 5, then one of those is the message from $A_{16}$. This implies that the government can intercept at most 9 different messages.

Furthermore, this number of days is optimal because of the following argument:

Let $M_i$ denote the first message which contains $F_i$ for any $0 \leq i \leq 16$. I claim that if $i \neq j$, then $M_i \neq M_j$: Suppose without loss of generality that the first time that $M_i$ is sent is before or on the same day as the first time $M_j$ is sent. Now $M_i$ is send by $A_i$, who cannot know $F_j$ at the time of sending, so $M_i$ does not contain $F_j$, while $M_j$ does.

So at least $17$ different messages have to be sent, now it is easy to see that these cannot be send on just 3 days without there being two days with a total of 10 different messages at the post office.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ typo: you forgot to send F16. note: You could just send F13 to everyone on day 1 (and then simplify the strategy a bit) $\endgroup$ – Retudin Oct 24 at 13:30
  • $\begingroup$ @Retudin thanks for the tip, I applied it in my post! I have also added an optimality proof now. $\endgroup$ – Reinier Oct 25 at 14:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.