12
$\begingroup$

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.]]

$\endgroup$
  • 2
    $\begingroup$ Is this a puzzle you created yourself, or that you got from elsewhere? If it's not original, please provide attribution to whoever created it. Puzzles without attribution will be closed. $\endgroup$ – bobble Oct 3 at 20:50
  • $\begingroup$ Questions like this in a random pairing setting are well studied in graph theory/information broadcasting; This specific question is about the upper bounds and the worst case for the information to spread. But this specific formulation is not mine, someone asked me this question, I don't have a source; $\endgroup$ – PoissonSummation Oct 3 at 20:56
  • 1
    $\begingroup$ By splitting 2020 into 101 groups of 20 people each, and using matchings internally inside a group and externally between the groups, I can get an algorithm which lasts for 1901 minutes. It's not clear if this is optimal. $\endgroup$ – PoissonSummation Oct 4 at 2:22
  • 1
    $\begingroup$ @PoissonSummation Don't spoiler your own puzzle! Or at least wait a few days. $\endgroup$ – Paul Panzer Oct 4 at 2:32
  • 1
    $\begingroup$ "...1901 minutes. It's not clear if this is optimal." It is not, see my edited answer. $\endgroup$ – Paul Panzer Oct 5 at 7:35
5
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Nice! I also observed that the even iterations for matching between groups don't have "self-loops" (in some cases) But I didn't think that the gain from these extra matchings will exceed the loss from splitting N into a product of very unequal numbers! $\endgroup$ – PoissonSummation Oct 5 at 20:38
  • $\begingroup$ @PoissonSummation Yes, it does feel a bit counter-intuitive. But one can actually check that if $m$ is odd and $n$ is even it's always worth halving $n$ and doubling $m$. $\endgroup$ – Paul Panzer Oct 5 at 21:03

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.