主題
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。


另請參閱

雞尾酒會圖, 握手問題, 聚會問題

在 中探索

參考文獻

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.

在 上引用

手套問題

請引用為

Weisstein, Eric W. "手套問題。" 來自 Web 資源。 https://mathworld.tw/GloveProblem.html

主題分類