離散數學(組合數學)題目問答

傲月光希

1.
mn 個人要排成 mXn 的長方陣，先隨便亂排，現在要求每列由矮排到高，排完後，再要求每行由矮排到高，證明此時每列也是由矮排到高。

2.
男女主人在門口招呼來參加宴會的 n 對夫婦，大家在一陣寒喧握手後，男主人問所有賓客和太太與別人握過幾次手，得到2n+1個不同答案，夫婦之間不握手，請問女主人握了幾次手?請證明你的答案。(HINT：只有一解)

3.
在一所8X8方格的監獄中，相鄰的牢房都有一個門相通，對外的門則鎖著，必須用鑰匙才能打開，如下圖：

┌─┬─┬─┬─┬─┬─┬─┬─┐
│。│　│　│　│　│　│　│　│
├─┼─┼─┼─┼─┼─┼─┼─┤
│　│　│　│　│　│　│　│　│
├─┼─┼─┼─┼─┼─┼─┼─┤
│　│　│　│　│　│　│　│　│
├─┼─┼─┼─┼─┼─┼─┼─┤
│　│　│　│　│　│　│　│　│
├─┼─┼─┼─┼─┼─┼─┼─┤
│　│　│　│　│　│　│　│　│
├─┼─┼─┼─┼─┼─┼─┼─┤
│　│　│　│　│　│　│　│　│
├─┼─┼─┼─┼─┼─┼─┼─┤
│　│　│　│　│　│　│　│　│
├─┼─┼─┼─┼─┼─┼─┼─┤
│　│　│　│　│　│　│　│。│
└─┴─┴─┴─┴─┴─┴─┴─┘
有一天，典獄長對一位死刑犯說：「你到左上角的那一間牢房，我在右下角的牢房等你，只要你能夠每個牢房都恰好經過一次，當你見到我的時候，我便放你自由。」現在請你幫這位死刑犯爭取自由。

取自 我的離散講義

[ 本文最後由 傲月光希 於 06-9-30 10:48 PM 編輯 ]

傲月光希

原文由 自得其樂 於 06-10-4 11:38 AM 發表
我猜是2N-1

==================
人數是2N+2
一個人最多握了2N次的手

男主人問了2N+1個人,得2N+1個答案,
因此被問到的每個人握手數都不同
必有一人握手 ...

不對唷，再加油