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

傲月光希

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

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

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

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

取自 我的離散講義

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

turnX

第三題
出處:圖論,拓樸學
那個犯人無法逃出!
把路徑圖化為二分圖...發現這兩房間在二分圖同一邊! 二分圖點數相等所以有漢米諾頓路徑和環路(一個定理)但這兩房間並非同一點.所以沒有環路.而路徑最後結束要是另一邊的點.所以是無解!不可能...

turnX

是有個初步想法

把這矩陣右轉45度...看做一連通網.想像一多泡泡(mn個人)在連通網中...這些接點有個閥門....
想像是可以想得出來...

證明...尚在找好的解釋方法...

turnX

可以用圖形去解釋...
由於row已經排好...所以我們去看相鄰的兩個column...
只要解釋相鄰兩column...
後一個column有一個數A大於比前一個column和目前的column所有n+(n-1)個數都大(假設n個)
後一個column有一個數B大於比前一個column和目前的column有n+(n-2)+數都大
後一個column有一個數C大於比前一個column和目前的column有n+(n-3)數都大
.
.
.

證於此...無論column如何排序皆可維持row已經排序.
可用圖形解釋...

[ 本文最後由 turnX 於 06-12-21 11:56 PM 編輯 ]

turnX

沒有限定怎麼握的情況下...在n+1對夫婦(其中1為男女主人)...共有2n+2個人!
而握手對象不是丈夫或妻子.自己也不可能和自己握手...所以最多的握手數是2n次
握手的可能的範圍是0~2n次...有2n+1種解...
而扣除男主人...剩下的2n+1個人對到2n+1個解=>不知道女主人是握幾次只知範圍
所以女主人握手數...有好多解!!

目前看不出題目有暗藏何種線索.....
也許這題我想法錯誤....

嗯...我忽略了男主人............
等等po上~
這也好像可轉化成圖形問題...

n次吧!...
想辦法解釋中.........

[ 本文最後由 turnX 於 06-10-1 07:23 AM 編輯 ]

自得其樂

我猜是2N-1

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

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

女主人的握手數:

必不為零.若為零,賓客中必有人握手數為零,答案重覆.

不為2N,賓客人數2N,女主人不跟男主人握,所以必和所賓客握過手,不符必有一人握手數為0.

不為1~2N-2,因為如此一來必有二人以上答案相同.

所以應該是2N-1,女主人有和一個賓客沒握到手,這人握手數應為0,賓客中應有一人只和女主人握過手.

================
不知道對不對就是了.

傲月光希

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

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

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

不對唷，再加油

自得其樂

原文由 傲月光希 於 06-10-4 08:34 PM 發表

不對唷，再加油

看來應該是忘了把蹲在角落劃圈圈的男主人算進去了，嗯，重新來過。




參加宴會的有ｎ對夫婦，加男女主人共２ｎ＋２，一個人最多握手２ｎ次。

男主人問了２ｎ＋１個人，得２ｎ＋１個答案，答案落在０～２ｎ的範圍，
且０和２ｎ為同一對夫婦，並不為主人夫婦。

扣掉這對夫婦（假設是甲夫婦）
男主人問了２ｎ－２對夫婦和自己太太，得２ｎ－１個答案，答案落在１～２ｎ－１範圍。
且握手數１和２ｎ－１為同一對夫婦，且不為主人夫婦。

（握２ｎ－１的那個人是除了甲夫婦和其餘２ｎ－２（加男女主人）個人握手，再加上和甲夫婦握過的那一次手）

再扣掉這對夫婦
男主人問了２ｎ－４對夫婦和自己太太，得２ｎ－３個答案，答案落在２～２ｎ－２

握手數２和２ｎ－２為同一對夫婦，且不為主人夫婦。


整理如下


被扣掉的夫婦數＼剩下的總人數　　＼男主人問了幾個人＼得到的答案數＼答案上限　＼答案下限
　　０　　　　＼２ｎ＋２　　　　＼　２ｎ＋１　　　＼　２ｎ＋１　＼　　２ｎ　＼　　０
　　１　　　　＼２ｎ　　　　　　＼　２ｎ－１　　　＼　２ｎ－１　＼　２ｎ－１＼　　１
　　３　　　　＼２ｎ－４　　　　＼　２ｎ－３　　　＼　２ｎ－３　＼　２ｎ－２＼　　２

　　Ｘ　　　　＼２（ｎ－ｘ＋１）＼　　　　　　　　　　　　　　　＼　　　　　＼　　
　　　　　　＝２ｎ－２ｘ＋２　　＼２ｎ－２ｘ＋１　＼　　　　　　＼ｙ　　　　＼　　ｘ


ｙ＝剩下的總人數－２（夫婦不互相握手，自己也不和自己握手）＋ｘ＝２ｎ－２ｘ＋ｘ

答案上限和答案下限相同即為主人太太的握手數

２ｎ－ｘ＝ｘ，ｎ＝ｘ


即主人太太的握手數為ｎ




嗯，愈證愈心虛