策略游戏：医生和病人（I）

我很早之前就想过这个问题，但一直只知道一个 trivial 的答案。前两天无意中发现网上已经有高手给出了更好的方案，故记录在此。有兴趣的可以自己想一想。

岛国上流行一种极易接触传染的病
一旦染上该病 1 月后病发身亡
但该病可通外科手术治愈

岛上每个人都有已被传染的可能
国王怀疑自己得了该病
在该岛上找到了医术最高名的 3 个医生
并要求这 3 个医生在当天轮流给自己动手术
然而已消毒过的手术手套只有 2 双
怎样最安全

现在把问题一般化，假设岛上有 n 个医生，还有 m 个（非医生）居民。现在岛上流行一种极易接触传染的病。每个居民要想治愈传染病，必须得到这 n 个医生的治疗，治疗的顺序无所谓（先别管这种假设的由来）。怎么安排它们手术的次序和带手套的方案，使得所用的手术手套最少。

注一：医生也有可能已被传染，故他们之间也要防止相互感染。
注二：手套可以套着用...还可以反着用...

下面的解答作者是 JtR ，来自水母 IQDoor 版。

用m/2+n/2+n/4m/2+n/2+n/4(m≤nm≤n)双手套即可。表示向上取整。

为了叙述方便，假设 m 是 2 的倍数， n 是 4 的倍数，不是 4 的倍数时类似，只是手套的「利用率」没有那么高。可能可以通过优化减少一副到两副。

1.将医生平均分为两组，分别为 A ， B。各 m/2 人；
将病人分为三组，人数分别为 a ＝ n/2 ， b=n/4 ， c=n/4

2.将 m/2 副手套分配给 A ， n/2 副手套分配给 a ， A 中的每一个医生检查 a 中的每一个病人；
检查前均在自己的手套外套上指定给该病人的手套；
注意所有的手套均只有一面污染。（假设医生之间也要防止相互感染）

3.将分配给 a 的 n/2 副手套中的一半翻转，两两一组套在一起，污染面互相接触，此时每一组手套内外均无污染；将这 n/4 组手套分配给 b(n/4 人）；
将剩下的未使用过的 n/4 只手套分配给 c(n/4 人）；

4.A 中的每一位医生分别检查 b ， c 中的病人，检查前均在自己的手套外套上指定给该病人的手套（或两只套在一起的手套）；
这样 A 中的医生完成对所有病人的检查，而且医生的手套外侧和指定给病人的手套内侧(注意有 n/4 是翻转过的)均无污染。

5.A 中所有的医生将各自的手套翻转后给 B 中的医生戴上；
b 中的病人把套在一起的手套里面的那只抽出来翻转后套入 c 组病人的手套中。此时 c 组的手套每一组相互接触的面都是干净的；

6.B 中所有的医生按前述方法给 b ， c 两组病人检查；

7.将 c 组的手套两两分开，把套在外面的手套翻转，这样得到 n/2 只外侧干净的手套重新分配给 a 组的病人。

8.B 中的所有医生检查 a 组的病人。

这样就完成了所有医生对病人的检查。

如果医生的数量比病人多只要把医生和病人交换即可。在该问题中二者是对称的。

Q. E. D.