Puzzle sur les infections (diffusion de l'information)

Question

Il y a 2020 personnes dans une salle. Une personne a un COVID.

Après chaque minute, chaque personne $\mathrm{P}$ est jumelé avec une autre personne $\mathrm{Q}$ qui n'a jamais été jumelé avec $\mathrm{P}$avant, et ils se toussent. Si l'un des$\mathrm{P}$ et $\mathrm{Q}$a COVID et d'autres pas, l'autre obtient COVID. Si les deux n'ont pas COVID ou les deux ont COVID, rien ne se passe.

Si vous pouvez choisir les personnes de chaque paire pour chaque minute et que vous souhaitez retarder le plus longtemps possible l'infection de tout le monde, combien de temps faudrait-il à tout le monde dans la pièce pour obtenir le COVID?

(La réponse semble dépendre beaucoup du nombre de personnes N = 2020, et j'ai une stratégie pour obtenir m ^ 2-2m + 1 minutes si N = m ^ 2, je ne suis pas sûr que ce soit optimal)

[[Des questions comme celle-ci dans un contexte d'appariement aléatoire sont bien étudiées en théorie des graphes / diffusion d'informations; Cette question concerne les limites supérieures et le pire des cas pour que l'information / l'infection se propage. Mais cette formulation spécifique n'est pas la mienne, quelqu'un m'a récemment posé cette question, je n'ai pas la source, mais c'est probablement d'un groupe Facebook «en fait de bons problèmes de mathématiques» auxquels je n'ai pas accès.]]

Answer 1

Je vais en tant que ligne de base expliquer la solution à laquelle OP fait allusion (pas seulement pour 2020, mais pour les nombres pairs qui se factorisent comme $N=2mn$). Ensuite, je montrerai une amélioration facile pour même$m=2m'$ ce qui augmente la durée totale de $(m-1)(2n-1)$ à $m'(2n-1)+2(m'-1)n$. Ces chiffres ne comptent pas la minute où les toutes dernières personnes sont infectées. Si vous souhaitez inclure cette minute, ajoutez-en une à tous les totaux.

Séparé en $m$ groupes de taille $2n$chaque. Nous écrirons$P_{ij}$ pour le $j$-ème patient du groupe $i$. Nous le ferons une fois en base zéro car nous pouvons ensuite écrire intelligemment$P_{00}$ pour le patient zéro.

Maintenant, nous construisons le calendrier: il se composera de $m-1$ époques de $2n-1$minutes chacun. À n'importe quelle époque, chaque groupe sera soit apparié à un autre groupe, soit isolé. Les groupes isolés feront juste un round robin (d'où$2n-1$ minutes) groupes appariés $G_k,G_l$ peut par exemple exécuter $P_{ki}\sim P_{li}$ $i=0,...,2n-1$ dans la première minute,$P_{ki}\sim P_{l,i+1\mod 2n}$ dans la seconde et ainsi de suite jusqu'à $P_{ki}\sim P_{l,i-2\mod 2n}$. Nous notons que nous avons une pièce de rechange.

Il reste à donner un calendrier d'appariement, je ne le montre que pour même $m=2m'$, thr autre cas est très similaire:
Epoque 0:$(G_0)\Vert$ $(G_1,G_{2m'-1}),(G_2,G_{2m'-2}),...,(G_{m'})$
Époque 1: $(G_0,G_1)\Vert$ $(G_2,G_{2m'-1}),(G_3,G_{2m'-2}),...,(G_{m'},G_{m'+1})$
Époque 2: $(G_0,G_2),(G_1)\Vert$ $(G_3,G_{2m'-1}),(G_4,G_{2m'-2}),...,(G_{m'+1})$
Époque 3: $(G_0,G_3),(G_1,G_2)\Vert$ $(G_4,G_{2m'-1}),(G_5,G_{2m'-2}),...,(G_{m'+1},G_{m'+2})$
Époque 4: $(G_0,G_4),(G_1,G_3),(G_2)\Vert$ $(G_5,G_{2m'-1}),(G_6,G_{2m'-2}),...,(G_{m'+2})$
Époque 5: $(G_0,G_5),(G_1,G_4),(G_2,G_3)\Vert$ $(G_6,G_{2m'-1}),(G_7,G_{2m'-2}),...,(G_{m'+2},G_{m'+3})$
...
j'ai marqué la "limite de l'infection" avec$\Vert$.

Amélioration pour même $m=2m'$:

Nous pouvons voir que toutes les autres époques n'ont pas de groupes non appariés. Comme indiqué ci-dessus, nous avons une minute de réserve dans chaque jumelage de groupe. Puisqu'il y a$m'-1$ ces époques (Le $m'$-th est différent car il se termine après sa première minute.) nous obtenons $(2n-1)(m-1) + m'-1 = 2n(m'-1) + (2n-1)m'$ minutes.

Amélioration pour 2020:

La solution OP est basée sur la division $m=101,n=10$ Changeons cela en $m=202,n=5$ nous permettant d'utiliser le même $m$amélioration. Cela donne$101\times 9 + 100 \times 10 = 1909$ (ou $1910$ si vous comptez la minute où le dernier groupe de personnes est complètement infecté), ce qui est légèrement mieux.