感染晚宴 II

Infected Dinner II

专题: Brainteaser / 脑筋急转弯
难度: L6
来源: QuantQuestion

题目详情

大厅里有 1000 人聚餐，其中 1 人已知生病，另外 999 人健康。每分钟每个人随机与大厅中的另一个人交谈。

但规则变为：每个人不会与自己曾经交谈过的人再次交谈（即每对人最多交谈一次）。

若一方生病一方健康，则健康者被感染并从此一直生病。

问：使得全员都生病的最长时间（分钟）是多少？

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.

解析

一种构造把 1000 人分成 25 个“泡泡”，每个泡泡 40 人。

通过安排，让感染在很长一段时间内只在部分泡泡中传播，而某个泡泡（包含最后的健康者）尽可能久都不与感染者产生交谈。

按该构造可使最后一个泡泡在前 24 轮（每轮 39 分钟）内都不被触达，总计 $24\times 39=936$ 分钟仍可能保持健康；在第 937 分钟让其与已感染泡泡接触即可全员感染。

因此最长可达 937 分钟。

Original Explanation

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 \hspace{3pt} \text{mod} \hspace{3pt} 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,\dots, k-1$ . This is since at round $1$ , Bubble $25$ talks with itself. Afterwards, it talks with Bubbles $1,2,\dots, k-1$ . Therefore, Bubble $24$ will be completely untouched until after the first $24$ rounds, which is $936$ minutes. Then, in the $937$ th minute, everyone in the $24$ th bubble talks to everyone in the $25$ th bubble, meaning all are infected in the first minute. Therefore, after $937$ minutes, everyone is infected.