[邏輯]pigeonhole旅館

[邏輯]pigeonhole旅館

訪客 於 星期五 五月 23, 2008 7:46 pm


話說 有100名成員的梅式(math)旅行團來到一個觀光景點,
但方圓百里之內僅有一家名為皮菌厚(pigeonhole)的旅館,
所以 旅團的人不得不在這旅館住宿.
雖然旅館每間都是空房, 但是總共也才90間房間.
而且梅式旅行團的團員們彼此之間非常不合, 所以要求一定要自己一間房睡.
好在 旅團的人每晚總是會有10個人在外遊蕩,
也就是說只會剩90人需要房間過夜.

(1). 如果你是皮菌厚旅館老闆, 最少要打幾把鑰匙給梅式旅行團, 才能讓每個團員每晚都有各自的房間安睡, 而不用來向你拿房間鑰匙, 也不用需要團員間彼此交換鑰匙.
(2). 又該如何分配那些鑰匙給團員呢?
(3). 又為什麼不能再少呢? (也就是說 請說明 (1) 的答案的理由)

舉個例子好了 :
1. 如果 給每人90把不同房間鑰匙的話, 不論剩下哪90人 要住宿的人總是可以打的開空房睡上一晚. 但是這樣一來 就需要100*90=9000把, 但這不會是最少的數量.
2. 假設 A 和 B 是旅團成員, A 有 1 和 2 號房的鑰匙 但是 B 只有 1 號房的鑰匙. 如果 A 已經在 1 號房 但 B 還沒有房間睡, 這時 B 可以請 A 換到 2 號房, 於是 A 和 B 就都有房可睡.
同理 90個人 彼此也可以互相商量好, 在不交換鑰匙的情況下都能有房間可睡

訪客

 

binglee 於 星期五 五月 23, 2008 10:11 pm


題意應該是任選10人在外遊蕩均可

如果是這樣,表示每間房間的鑰匙數不得少於11把

因為如果任一間房間的鑰匙數少於11把,
持有這間房間鑰匙的人如果同時在外遊蕩,就會造成這個房間無法開啟
根據鴿籠原理(PigeonHole Principle)可知,這90間房間無法容納90人

故每個房間打11把鑰匙,共需11*90=990把
亦即鑰匙總數不得小於11*90=990把...(1)(3)

(2)
將人編號1~100號
1~90號人各別拿1~90號房的鑰匙(每人身上恰1把)
然後91~100號成員拿全部房間的鑰匙(每人身上恰90把)

選房間時,前90號的人先選房間
剩下的房間,再由後10號的人任選即可
其實,一個人過日子也還不錯
只是,有妳在身邊一切更美好

binglee
研究生
研究生
 
文章: 118
註冊時間: 2006-02-22
來自: Taiwan




邏輯推理學院