病毒感染问题 #

题目 #

一种新型流感开始传播. 健康的人与感染的人有过接触后, 第二天会被感染; 感染的人第二天会痊愈, 并且拥有时效为 $1$ 天的抗体, 有抗体的情况下与感染者接触第二天不会被感染. 假设每个人每天都会与所有认识的人接触. 证明:

1. 如果有人开始拥有时效一天的抗体, 那么流感可能永远不会结束
2. 如果开始时所有人都没有抗体, 那么流感迟早会结束.

解答 #

考虑以下模型: 有 $3$ 个人, 开始分别处于健康、感染与抗体状态, 且他们互相认识. 容易验证此时流感永远不会结束. 第 1 问得证.

对于第 2 问, 把每个人看成一个节点, 两个人如果互相认识则连一条边. $x, y$ 之间的距离为最短路径的长度, 记为 $d(x, y)$ . 记初始时间第 $0$ 日的感染者集合为 $P$ , 按到集合 $P$ 的最短距离将人群划分为 $S_0(=P), S_1, S_2, …$ , 其中 $S_k = {x\vert \underset{y\in P}{min}\ d(x, y) = k}$ . 下面来证明第 $k$ 日的感染者集合为 $S_k$ .

• 第 $0, 1$ 日, 感染者集合分别为 $S_0(=P)$ , $S_1$.

• 假设结论对 $n = k - 1, k$ 成立, 考虑 $n = k + 1$ . 第 $k+1$ 天的感染者来自第 $k$ 天与 $S_k$ 接触的健康人群.

  • 对于 $0\leq i\leq k - 2$ , $S_i$ 与 $S_k$ 不可能有边相连, 否则与 $S$ 的定义矛盾. 因此, 第 $k + 1$ 天的感染者不可能来自 $S_i$ , $0\leq i\leq k - 2$ ;
  • 对于 $i\geq k + 2$ 的 $S_i$ 不可能称为第 $k + 1$ 天的感染者, 理由同上;
  • 对于 $S_{k - 1}$ , 由假设知, 他们在第 $k - 1$ 天感染并在第 $k$ 天痊愈并拥有抗体. 因此, 第 $k + 1$ 天的感染者不可能来自 $S_{k - 1}$ ;
  • 对于 $x\in S_{k + 1}$ , 假设 $d(x, y) = k+1, y\in P$ , 考虑最短路径上的离 $x$ 最近的那一点 $z$ , 有 $d(z, y) = k$ , 因此 $z\in S_k$ , 因此 $\forall x\in S_{k+1}$ , 在 $k+1$ 天都会成为感染者.

  故结论对 $n = k + 1$ 也成立.

综上, 第 $k$ 日的感染者集合为 $S_k$ . 显然人数是有限的, 因此距离也有限. 记节点集为 $V$ , $m = \underset{x\in V, y\in P}{max}\ d(x, y)$ , 那么第 $m + 1$ 的感染者集合为 $S_{m+1} = \emptyset$ , 也就是说流感会在 $m + 1$ 天结束.