感染晚宴 I

Infected Dinner I

专题: Brainteaser / 脑筋急转弯
难度: L4
来源: 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. There is no limit on how many times a person talks to another person. 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 minimum amount of time (in minutes) until every person in the hall becomes sick.

解析

要最短，就让每个已感染者每分钟都和一名健康者交谈，从而感染人数每分钟翻倍：

1 分钟后：2 人感染。
2 分钟后：4 人感染。
一般地， $n$ 分钟后： $2^n$ 人感染。

求最小 $n$ 使 $2^n>1000$ ，因为 $2^{10}=1024$ ，所以最短为 10 分钟。

Original Explanation

The minimum amount of time would correspond to the most people becoming infected the fastest. This would be when each infected person talks to a healthy person at every step. After $1$ minute, there would be $2$ infected people. After $2$ minutes, there would be $4$ infected people, as each of the $2$ infected people talks to someone healthy. In general, after $n$ minutes, there would be $2^n$ infected people. We now just have to find the minimum $n$ such that $2^n > 1000$ , which is just $n = 10$ .