Infected Dinner Brainteaser

Question

I came across this brainteaser online that I found quite confusing:

There are $1000$ people having dinner at a grand hall. One of them is known to be sick, while the other $999$ are healthy. Each minute, each person talks to one other person in the room at random. However, as everyone is social, nobody talks to people they have previously talked to. In each pair, if one is sick and one is healthy, the healthy person is infected and becomes sick. Once a person becomes sick, they are assumed to be sick for the rest of the dinner. Find the maximum amount of time (in minutes) until every person in the hall becomes sick.

This is the solution provided:

Consider grouping the $1000$ people into $25$ groups of $40$ people. In $25$ rounds of $39$ minutes each, every person in a given bubble talks to every other person in that bubble. additionally, each of the other bubbles are paired up.

Suppose the original sick person is in Bubble $25$ and the last healthy person is in Bubble $24$. In round $k$, we can have all the people in bubble $b$ talk to all of the people in bubble $24 - b + k \mod 25$, where $0$ maps to $25$. Therefore, we see that after $k$ rounds, the sick people belong to people in Bubble $25$ and Bubbles $1, 2, \ldots, k-1$. This since at round $1$, Bubble $25$ talks with itself. Afterwards, it talks with Bubbles $1, 2, \ldots, k-1$. Therefore, Bubble $24$ will be completely untouched until after the first $24$ rounds, which is $936$ minutes. Thus, we add in $39$ minutes for the last round, and we have $975$ minutes. However, note that each round is $39$ minutes long. Therefore, every Bubble that isn't Bubble $25$ is going to have exactly $1$ person that is not sick still. We must add in $24$ minutes for those $24$ people to become sick, so our answer is $999$.

[Editor's note: the original image can be found here.]

I don't quite understand the solution / I think it might be wrong, since it doesn't consider the fact that everyone must be talking and not just the individual groups (where the remaining groups are doing nothing). Perhaps I misread something but any insight would be much appreciated!

Edit: The original question was taken from here: https://www.quantguide.io/questions/infected-dinner-ii

Also I apologize if my question wasn't clear. Since we want to find the maximum bound on the time needed to guarantee that everyone is sick, we would probably want to maximize the number of times a sick individual talks to another sick individual, with the restriction of being unable to talk to someone they previously talked to. This seems to be a lot of information to keep track of and I'm not sure how to reduce the problem/represent it so that its easier to understand and compute the answer. I guess my question would be: Is there a better way to represent the problem to make it easier to understand how to go about finding a solution?

Answer 1

Their solution has many mistakes. As far as I can tell, when you fix those mistakes, the time they attain is only $937$ minutes.

First, let us clarify what they mean. There are $25$ bubbles, numbered $B_1,B_2,\dots,B_{25}$, each with $40$ people. There are $25$ rounds, $R_1,R_2,\dots,R_{25}$, each lasting $39$ minutes. For each $k\in \{1,\dots,25\}$ and each $b\in \{1,\dots,25\}$, during round $R_k$, all of the people in $B_b$ will only talk to people to people in $B_{24+k-b\pmod{25}}$. However, the problem did not specify the exact way to pair people up which allows this to happen.

Here are the missing details of how to pair people up:

• In order to have two different groups, $B_i$ and $B_j$ with $i\neq j$, talk to only each other over the course of $39$ minutes, you match them up randomly in a circle for the first minute, and then rotate everyone in $B_i$ one spot to the right for each of the remaining $38$ minutes (while the people in $B_j$ stay put).

• In order to have $B_i$ members only talk to themselves over the course of $39$ minutes, use the classic round robin tournament schedule.

Onto the mistakes the solution makes. First of all, notice in round $R_1$, bubble $B_{25}$ talks to itself. This means that everyone in $B_{25}$ becomes infected after round $1$. It does not matter how you arrange the connections; the initial infected person must talk to $39$ different people during this period, so everyone else in $B_{25}$ is infected at the end. In particular, later when $B_{25}$ talks to another bubble, that bubble gets completely infected.

Now, the solution correctly claims that after round $k$, the infected bubbles are $B_{25},B_1,\dots,B_{k-1}$. This means that after $24$ rounds ($936$ minutes), every bubble except $B_{24}$ is completely infected. Then, in the $937^\text{th}$ minute, everyone in $B_{24}$ talks to everyone in $B_{25}$, which means everyone in $B_{24}$ is immediately infected.

• The solution mistakenly adds in the $39$ minutes for the last round; you cannot count this time, because everyone was already sick after the first minute of $R_{25}$.

• The solution then goes on to say that there is still $1$ uninfected person in each bubble besides $B_{25}$, so you need to add in $24$ minutes for these people. This is nonsense, because we already showed that every bubble gets completely infected when it talks to $B_{25}$.

Answer 2

All of the answers above are incorrect enough...they all disregard the difference of "talking to itself" or "talking to a different group", especially when this problem is asking "maximum" time.

A universal solution:

An intuition (not so rigorous) of "max time" is that, if we separate the path of infection as binary trees, one infected needs to try his best to find the other one who is already infected but in a same binary tree, i.e. share the same final parenting nodes. Another intuition is that, the "max time" should be close to linear, rather than exponential increase. So we tried to keep the total time linearly increase. This is to say, we would like to let "some" infected people talk to innocent ones in each round, while keep other infected ones talk within the infected community.

In that case, if we separate the total 1000 people into $m$ trees, or $m$ bubbles (more understandable). Then we list the $k-th$ permutation of $[1,...,m]$ as the group paired to the original group in the round $k$. This is to say, if we have a permutation like $[1,4,3,2] (say, if m=4)$, this means the bubble 1 talks to the bubble 1, and bubble 2 talks to the bubble 4, the bubble 3 talks to itself, the bubble 4 talks to the bubble 2. Within each round, say if we focus on "the bubble 2 talks to the bubble 4" (or other, they are intrinsically same), the tree, or the bubble, would have $1000/m$ minutes to let each individuals in bubble 2 talks to every one in the bubble 4. But if one bubble talks to itself, the time would be $1000/m - 1$.

Then for the round 1, the intuition 1 tell us we need to let the bubble which contains the infection talk to itself. This is because right now it's just the first round, we need to keep the infection as small as possible. Every "+1" in the beginning would make the total time decrease. (Ps, this is also one thought in Exponentiation by squaring, if you got any other time, you can consider a similar problem, write an algorithm to calculate the min steps you need to decompose 100 to 1, you can only choose 3 options: 1) $n-=1$; 2) $n/=2$, 3) $n/=3$. The option 2) and 3) only happens if $n%2=0$ or $n%3=04$.

Go back to this problem, after the first round, only one bubble gets totally infected, say it's the $m-th$ one, i.e. the infection set is $(m)$. Then in the second round, suppose we pair $n-th$ bubble to the $m-th$ one, the infection set increases to $(m, n)$.

The problem comes when the third round comes, suppose a new group is paired to $m$, who should $n$ talk to? the problem is asking the "max time", so it seems that $n$ cannot talk to a new one to enlarge the total time as longest as possible. So here we'd like to let $n$ talk to itself. This means, in the first round, $n$ cannot talk to itself. Here comes the third intuition:

Intuition 3: any group except the $m-th$ bubble should talk to itself as later as they could.

Then for the fourth-round, now we have $(m,n,k)$ as the infection set, suppose $m$ choose $l$ as the new infected group, then $n$ could talk to $k$, this is good. Infection set becomes $(m,n,k,l)$.

For the fifth-round, $l$ goes to $n$, $k$ goes to itself, $m$ goes to a new one...

So here we can see, things changed for different round. Typically, if in the current round, the length of the infection set is odd, $m$ goes to new one, then the other infected bubble would be paired up. But if the length of the infection set is even, one infected bubble needs to talk to itself. For the other one, the oldest just came to the latest joined member, the second oldest bubble came to the last second infected member...The one who needs to talk to itself should be the $(k-1)/2 -th$ bubble in each even round. This is to say, if before the $k-th$ round, the infection group is $(6,1,2,...,k-2)$, then in $k-th$ round (if k is odd), $m=6 th$ bubble talks to the $k-1 -th$ bubble who is innocent, $1st$ bubble talk to $k-2 th$, $2nd$ bubble talk to $k-3$, ..., the $(k-1)/2-th$ needs to talk to itself. If $k$ is even, then this situation does not happen.

WLOG, let the infection set be $(m)$, $(m,1)$, $(m,1,2)$, $(m,1,2,3)$,...,$(m,1,2,3,..,m-1)$, this is to say, the permutation of each round would be (if we rotate it):

[m-1,m-2,...,1,m]

[m,m-1,m-2,...,1]

[1,m-1,m-2,...,2]

[2,1,m-1,...,3]

...

[m-2,m-3,m-4,...,m-1]

Meanwhile, we need to mention that, in the odd round, it is possible that normal bubble who is going to talk to itself. If $m$ is even, then this happens in odd round (on $m/2 -th$ bubble), if it's odd, it happens on even round (on $m$).

So assume $m$ is odd, each round takes $1000/m-1$ minutes, because each round we have a bubble talk to itself. So the total min would be $(1000/m-1)*(m-1)$ when the $m-2$ round ends. Then in next minutes, each person in $m-1 -th$ bubble talks to $m-th$ bubble and gets infected. Optimize $(1000/m-1)*(m-1)$ given $m$ is an odd integer and also a factor of 1000 yields $m=25$, the total min is $(1000/25-1)*(25-1)+1=937$.

Assume $m$ is even, things are far more complicated because there are some rounds the time would be $1000/m$. There would be $m/2$ rounds of $1000/m$ and $m/2-1$ rounds of $1000/m-1$ (just consider $m=4$, only the first and third round has groups who talk to themselves). So the total time should be $(1000/m)*m/2 + (1000/m-1)*(m/2-1)+1$, optimize it and get $m=40 or 50$ and total time is 957.

(Btw: The case $m$ is even is a bit complicated, because we need to ensure the infected group which needs to talk to itself in round $k$ does not talk to itself before this round (i.e. when it is innocent). This is because there could be multiple bubbles which talk to themselves in one round when $m$ is even. See this case when $m=6$:

1 2 3 4 5 6

5 4 [3] 2 1 6

6 5 4 3 2 1

[1] 6 5 4 3 2

...

3 [2] 1 6 [5] 4