Infektionsrätsel (Informationsverbreitung)

Question

In einem Raum sind 2020 Personen. Eine Person hat COVID.

Nach jeder Minute jede Person $\mathrm{P}$ ist mit einer anderen Person gepaart $\mathrm{Q}$ mit wem wurde nie gepaart $\mathrm{P}$vorher, und sie husten miteinander. Wenn einer von$\mathrm{P}$ und $\mathrm{Q}$hat COVID und andere nicht, der andere bekommt COVID. Wenn beide kein COVID haben oder beide COVID haben, passiert nichts.

Wenn Sie die Personen in jedem Paar für jede Minute auswählen können und Sie möchten, dass alle infiziert werden, so lange wie möglich, wie lange würde es dann dauern, bis alle im Raum COVID erhalten?

(Die Antwort scheint stark von der Anzahl der Personen N = 2020 abzuhängen, und ich habe eine Strategie, um m ^ 2-2m + 1 Minuten zu erhalten, wenn N = m ^ 2, ich bin nicht sicher, ob dies optimal ist)

[[Fragen wie diese in einer zufälligen Paarungseinstellung sind in der Graphentheorie / Informationsübertragung gut untersucht; Bei dieser Frage geht es um die Obergrenzen und den schlimmsten Fall, dass sich die Informationen / Infektionen verbreiten. Aber diese spezielle Formulierung gehört nicht mir. Jemand hat mir kürzlich diese Frage gestellt. Ich habe keine Quelle. Aber sie stammt wahrscheinlich von einer Facebook-Gruppe mit „eigentlich guten mathematischen Problemen“, auf die ich keinen Zugriff habe.]]

Answer 1

Ich werde als Basis die Lösung formulieren, auf die OP hinweist (nicht nur für 2020, sondern auch für gerade Zahlen, die als faktorisieren $N=2mn$). Danach werde ich eine einfache Verbesserung für gerade zeigen$m=2m'$ was die Gesamtdauer von erhöht $(m-1)(2n-1)$ zu $m'(2n-1)+2(m'-1)n$. Diese Zahlen zählen nicht die Minute, in der die letzten Menschen infiziert sind. Wenn Sie diese Minute einschließen möchten, fügen Sie eine zu allen Summen hinzu.

Aufgeteilt in $m$ Gruppen von Größe $2n$jeder. Wir werden schreiben$P_{ij}$ für die $j$-th Patient in der Gruppe $i$. Wir machen das einmal auf Null, weil wir dann geschickt schreiben können$P_{00}$ für Patient Null.

Jetzt konstruieren wir den Zeitplan: Er wird bestehen aus $m-1$ Epochen von $2n-1$jeweils Minuten. Während jeder Epoche wird jede Gruppe entweder mit einer anderen Gruppe gepaart oder isoliert. Isolierte Gruppen machen nur ein Round Robin (daher$2n-1$ Minuten) gepaarte Gruppen $G_k,G_l$ kann zum Beispiel laufen $P_{ki}\sim P_{li}$ $i=0,...,2n-1$ in der ersten Minute$P_{ki}\sim P_{l,i+1\mod 2n}$ in der zweiten und so weiter bis $P_{ki}\sim P_{l,i-2\mod 2n}$. Wir stellen fest, dass wir einen Ersatz haben.

Es bleibt ein Paarungsplan zu geben, ich zeige ihn nur für gerade $m=2m'$Der andere Fall ist sehr ähnlich:
Epoche 0:$(G_0)\Vert$ $(G_1,G_{2m'-1}),(G_2,G_{2m'-2}),...,(G_{m'})$
Epoche 1: $(G_0,G_1)\Vert$ $(G_2,G_{2m'-1}),(G_3,G_{2m'-2}),...,(G_{m'},G_{m'+1})$
Epoche 2: $(G_0,G_2),(G_1)\Vert$ $(G_3,G_{2m'-1}),(G_4,G_{2m'-2}),...,(G_{m'+1})$
Epoche 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})$
Epoche 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})$
Epoche 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})$
...
Ich habe die "Infektionsgrenze" mit markiert$\Vert$.

Verbesserung für gerade $m=2m'$::

Wir können sehen, dass jede andere Epoche keine ungepaarten Gruppen hat. Wie oben erwähnt, haben wir in jeder Gruppenpaarung eine Minute Zeit. Weil dort sind$m'-1$ solche Epochen (The $m'$-th ist anders, da es nach seiner ersten Minute endet.) Wir bekommen $(2n-1)(m-1) + m'-1 = 2n(m'-1) + (2n-1)m'$ Protokoll.

Verbesserung für 2020:

Die OP-Lösung basiert auf Split $m=101,n=10$ Ändern wir das in $m=202,n=5$ so dass wir die gerade verwenden können $m$Verbesserung. Das gibt$101\times 9 + 100 \times 10 = 1909$ (oder $1910$ Wenn Sie die Minute zählen, in der die letzte Gruppe vollständig infiziert ist, ist dies etwas besser.