主题
Search

手套问题


假设有 m 位医生和 n<=m 位病人,并且所有 mn 可能的医生检查病人的组合都发生。那么,需要最少多少外科手套 G(m,n) 才能保证没有医生必须戴被病人污染的手套,也没有病人暴露于另一位医生戴过的手套(假设每位医生只在一只手上戴一只手套)?在这个问题中,手套可以翻过来,甚至可以在必要时叠放在一起,但不允许对手套进行“消毒”。最优解是

 g(m,n)={2   m=n=2; 1/2(m+1)   n=1, m=2k+1; [1/2(m)+2/3n]   otherwise,
(1)

其中 [x]向上取整函数 (Vardi 1991)。

m=n=2 时的情况很简单,因为两只手套总共有四个表面,这正是 mn=4 次检查所需的数量。对于医生 AB,病人 ab 和手套 12,一个解决方案是 A12a、A1b、B2a、B21b。


另请参阅

鸡尾酒会图, 握手问题, 聚会问题

在 Wolfram|Alpha 中探索

参考文献

Gardner, M. 啊哈!灵机一动。 New York: Scientific American, 1978.Gardner, M. 科幻谜题故事集。 New York: Crown, pp. 5, 67, and 104-150, 1981.Hajnal, A. and Lovász, L. "防止某些疾病以最低成本传播的算法。" §10.1 in 计算机科学与运筹学之间的接口:1976 年 9 月 7 日至 10 日在阿姆斯特丹数学中心举行的研讨会论文集 (Ed. J. K. Lenstra, A. H. G. Rinnooy Kan, and P. van Emde Boas). Amsterdam: Matematisch Centrum, 1978.Orlitzky, A. and Shepp, L. "关于遏制病毒传播。" 技术备忘录中的练习 10.2。 Bell Labs, 1989.Vardi, I. "避孕套问题。" 第 10 章 in Mathematica 中的计算娱乐。 Redwood City, CA: Addison-Wesley, pp. 203-222, 1991.

在 Wolfram|Alpha 上引用

手套问题

请引用为

Weisstein, Eric W. "手套问题。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/GloveProblem.html

主题分类