Espions à Puzzlevania

Question

Ce que je vais vous dire ne quitte pas cette pièce. Au cours de la dernière année, nous sommes devenus préoccupés par les événements dans la nation de Puzzlevania. Nous pensons qu’une attaque majeure pourrait être imminente. Cependant, le général refuse d'agir sans preuves plus concrètes d'une menace. À cette fin, nous nous préparons à envoyer 16 espions et un maître-espion dans la Puzzlevania pour une reconnaissance plus approfondie et une évaluation des menaces. Mais, il y a un hic.

Chaque agent doit partager ses conclusions avec les 16 autres pour s'assurer que tout le monde peut suivre le plan d'urgence approprié. Nos gens ont développé un code tel que tout message semble inoffensif (et non charabia) à un observateur ordinaire. Malheureusement, je viens d'être informé que Puzzlevania a un nouvel appareil qui sera capable de déchiffrer notre code à condition que 10 échantillons uniques.

L'envoi de communications électroniques est beaucoup trop risqué étant donné cet appareil. Notre seul espoir est de s'appuyer sur le système de messagerie traditionnel de Puzzlevania. Le courrier est normalement ramassé un jour, reste au centre postal pendant la nuit, puis livré le lendemain (Puzzlevania n'est pas si grande, donc un seul centre postal). Cependant, le courrier reste parfois plusieurs nuits, mais tout le courrier est finalement livré.

Les inspecteurs du gouvernement peuvent se présenter la nuit avec le dispositif de décryptage et le faire scanner chaque morceau de courrier dans le centre. Ils referment alors parfaitement tout le courrier et partent. Heureusement, d'autres sources indiquent qu'elles n'ont le budget que pour deux inspections supplémentaires cette année, et la coutume ancienne interdit de rechercher les courriers envoyés alors qu'ils n'ont pas de budget (même s'ils en reçoivent plus tard).

J'ai besoin que vous conceviez un système pour que tous les agents puissent envoyer leurs découvertes aux autres sans que Puzzlevania ne casse le code. Vous pouvez supposer que le maître-espion commence toutes les chaînes en fonction du timing. Bien sûr, le programme doit être aussi court que possible en supposant que tout le courrier est à l'heure.

Addition:

17 agents doivent envoyer leurs résultats par courrier.

Si 10 messages uniques sont interceptés, les agents portent un toast.

L'ennemi peut intercepter tous les messages dans le centre postal deux fois.

Le courrier prend normalement un jour pour arriver, mais peut prendre plus de temps.

Aucun courrier n'est jamais perdu (tout arrive finalement).

Le système doit fonctionner quel que soit le temps qu'il faut à un message particulier pour arriver.

Le schéma le plus court (compte tenu de tous les courriers à temps) gagne.

Des messages vierges peuvent être envoyés.

Answer 1

J'ai trouvé une solution en utilisant

4 jours, et c'est optimal.

Cela fonctionne comme suit:

Laisser $A_0, \ldots, A_{16}$ être les noms des agents, et laissez $F_0, \ldots, F_{16}$dénotent leurs découvertes.

Jour 1:
$A_0$ envoie $F_0$ à $A_1$
$A_4$ envoie $F_4$ à $A_5$
$A_8$ envoie $F_8$ à $A_9$
$A_{12}$ envoie $F_{12}$ à $A_{13}$
$A_{16}$ envoie $F_{16}$à tous les autres agents (exactement le même message est envoyé à chaque agent)

Jour 2:
$A_1$ envoie $F_0, F_1$ à $A_2$ (En un seul message!)
$A_5$ envoie $F_4, F_5$ à $A_6$
$A_9$ envoie $F_8, F_9$ à $A_{10}$
$A_{13}$ envoie $F_{12}, F_{13}$ à $A_{14}$

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

Jour 4:
$A_3$ envoie $F_0, F_1, F_2, F_3$ à tous les autres agents (exactement le même message est envoyé à chaque agent)
$A_7$ envoie $F_4, F_5, F_6, F_7$ à tous les autres agents
$A_{11}$ envoie $F_8, F_9, F_{10}, F_{11}$ à tous les autres agents
$A_{15}$ envoie $F_{12}, F_{13}, F_{14}, F_{15}$à tous les autres agents
Et maintenant, chaque agent a reçu tous les messages!

Dans le cas où un message est retardé, l'agent qui devrait recevoir ce message attend juste avec l'envoi de son prochain message jusqu'à ce que le message précédent ait été reçu.

La raison pour laquelle l'ennemi ne peut pas intercepter 10 messages différents:

Notez qu'à tout moment, il y a au plus 1 message de $A_0$ à $A_3$ au bureau de poste, au plus 1 message de $A_4$ à $A_7$, au plus 1 message de $A_8$ à $A_{11}$, au plus 1 messages de $A_{12}$ à $A_{15}$ et peut-être il y a le message envoyé par $A_{16}$. Il y a donc au plus 5 messages différents au bureau de poste à tout moment, et s'il y en a 5, l'un d'entre eux est le message de$A_{16}$. Cela implique que le gouvernement peut intercepter au plus 9 messages différents.

De plus, ce nombre de jours est optimal en raison de l'argument suivant:

Laisser $M_i$ désignent le premier message qui contient $F_i$ pour toute $0 \leq i \leq 16$. Je prétends que si$i \neq j$, ensuite $M_i \neq M_j$: Supposons sans perte de généralité que la première fois que $M_i$ est envoyé avant ou le même jour que la première fois $M_j$est envoyé. À présent$M_i$ est envoyé par $A_i$, qui ne peut pas savoir $F_j$ au moment de l'envoi, donc $M_i$ ne contient pas $F_j$, tandis que $M_j$Est-ce que.

Donc au moins$17$ différents messages doivent être envoyés, maintenant il est facile de voir que ceux-ci ne peuvent pas être envoyés en seulement 3 jours sans qu'il y ait deux jours avec un total de 10 messages différents au bureau de poste.