話說 有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個人 彼此也可以互相商量好, 在不交換鑰匙的情況下都能有房間可睡