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

作者: , 共 1233 字

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

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

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

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

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

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

\({m/2}+{n/2}+{n/4}\)(\(m\leq 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.

类似文章:
相似度: 0.123
Alice 和 Bob 两人玩一种硬币游戏。游戏在一个\( 2\times2\) 的棋盘上进行,棋盘上每个格子上都有一枚硬币。在每一回合, Alice 可以决定选择翻转某两枚或者一枚硬币,接着 Bob 可以选择将棋盘旋转 90 , 180 或者 270 度,也可以什么都不做。
相似度: 0.122
\( n\) 枚硬币排成一排,两人轮流取,每人每次可取其中一枚或者相邻的两枚。
相似度: 0.085
前两天贴出了一个硬币游戏,希望寻找一种胜利策略。这是一个非常有意思的题目,没事做的时候可以用来锻炼思考能力。我迫不及待的想在这里公布解答,因为我已经把它解决掉了。如果有人还想继续享受思考的乐趣,请飘至原问题
前一篇:
这个题目听说是 MSRA 的面试题。
数学 » Ponder this, 几何
今年 IBM 七月份的 Ponder This 问题(原题在这里,英文):