策略游戏:医生和病人(I)

作者:, 发表于

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

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

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

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

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

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

用{m/2}+{n/2}+{n/4}(m<=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组的病人。

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

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

[tags]医生和病人,策略,游戏[/tags]