Infection (Information Dissemination) Puzzle

Question

There are 2020 people in a room. One person has COVID.

After each minute, each person $\mathrm{P}$ is paired with some other person $\mathrm{Q}$ who was never paired with $\mathrm{P}$ before, and they cough to each other. If one of $\mathrm{P}$ and $\mathrm{Q}$ has COVID and other does not, the other gets COVID. If both do not have COVID or both have COVID, nothing happens.

If you can choose the people in each pair for every minute and you'd like to delay everyone getting infected for as long as possible, then how long would it take for everyone in the room to get COVID?

(The answer seems to depend a lot on the number of people N=2020, and I have a strategy to get m^2-2m+1 minutes if N=m^2, I am not sure if this is optimal)

[[Questions like this in a random pairing setting are well studied in graph theory/information broadcasting; This question is about the upper bounds and the worst case for the information/infection to spread. But this specific formulation is not mine, someone recently asked me this question, I don't have the source, But it's probably from some Facebook group “actually good math problems” which I don't have access to.]]

Answer 1

I'll as a base line spell out the solution OP is hinting at (not just for 2020 but for even numbers that factorize as $N=2mn$). Afterwards I'll show one easy improvement for even $m=2m'$ which increases the total duration from $(m-1)(2n-1)$ to $m'(2n-1)+2(m'-1)n$. These numbers are not counting the minute the very last people are infected. If you want to include this minute add one to all totals.

Split into $m$ groups of size $2n$ each. We'll write $P_{ij}$ for the $j$-th patient in group $i$. We'll do it zero-based this once because we can then cleverly write $P_{00}$ for patient zero.

Now we construct the schedule: It will consist of $m-1$ epochs of $2n-1$ minutes each. During any epoch each group will either be paired with one other group or isolated. Isolated groups will just do a round robin (hence $2n-1$ minutes) paired groups $G_k,G_l$ can for example run $P_{ki}\sim P_{li}$ $i=0,...,2n-1$ in the first minute,$P_{ki}\sim P_{l,i+1\mod 2n}$ in the second and so on until $P_{ki}\sim P_{l,i-2\mod 2n}$. We note that we have one spare.

It remains to give a pairing schedule, I only show it for even $m=2m'$, thr other case is very similar:
Epoch 0: $(G_0)\Vert$ $(G_1,G_{2m'-1}),(G_2,G_{2m'-2}),...,(G_{m'})$
Epoch 1: $(G_0,G_1)\Vert$ $(G_2,G_{2m'-1}),(G_3,G_{2m'-2}),...,(G_{m'},G_{m'+1})$
Epoch 2: $(G_0,G_2),(G_1)\Vert$ $(G_3,G_{2m'-1}),(G_4,G_{2m'-2}),...,(G_{m'+1})$
Epoch 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})$
Epoch 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})$
Epoch 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})$
...
I've marked the "infection boundary" with $\Vert$.

Improvement for even $m=2m'$:

We can see that every other epoch has no unpaired groups. As noted above we have one minute spare in each group pairing. Since there are $m'-1$ such epochs (The $m'$-th is different as it ends after its first minute.) we get $(2n-1)(m-1) + m'-1 = 2n(m'-1) + (2n-1)m'$ minutes.

Improvement for 2020:

OP solution is based on split $m=101,n=10$ Let us change that to $m=202,n=5$ allowing us to use the even $m$ improvement. This gives $101\times 9 + 100 \times 10 = 1909$ (or $1910$ if you count the minute the last group of people get infected in full) which is slightly better.