Quod Erat Demonstrandum

2008/07/15

婚姻定理

Filed under: Additional / Applied Mathematics,Pure Mathematics — johnmayhk @ 11:55 下午

看港台節目《改革開放三十年系列 – 中國新面貌》之《入贅女婿》才知近年國內『入贅女婿』這個『社會現象』頗為普遍。據《說文解字》,「贅,以物質錢,從敖貝,敖者獲放貝,當復取之也。」即是贅,有抵押、交換的意思。男子入贅成婚,就是以身作『抵押、交換』。愈看節目,心中愈有不可名狀的納悶。抽水完畢,還是說數學好了。

比如你是婚姻介紹所的負責人,以下四名女士,表達了她們心儀的結婚對象:

嘉玲:{敬軒,朝偉,力申}
苑之:{敬軒,朝偉,志安}
秀文:{朝偉,志安}
麗欣:{力申,敬軒}

在一夫一妻的前提下,請問如何把男士「配給」給那些女士?很簡單,比如:

嘉玲:{朝偉}
苑之:{敬軒}
秀文:{志安}
麗欣:{力申}

又或者

嘉玲:{力申}
苑之:{志安}
秀文:{朝偉}
麗欣:{敬軒}

以符號示之,可表為

A_1 = {1 , 2 , 3}
A_2 = {1 , 2 , 4}
A_3 = {2 , 4}
A_4 = {3 , 1}

其中一種『配給』方式是

A_1 : {2}
A_2 : {1}
A_3 : {4}
A_4 : {3}

分配工作容易吧?但可以想像,當女士人數不是 4 個,而是比較多(例如在生意好的情況下),分配工作未必太易。比如

A_1 = {1 , 2 , 3 , 4}
A_2 = {1 , 3 , 4 , 5 , 8}
A_3 = {3 , 5 , 7}
A_4 = {2 , 4}
A_5 = {1 , 2 , 5}
A_6 = {1 , 3 , 4 , 5}
A_7 = {2 , 4}
A_8 = {3 , 5 , 8}

就上述的例子,你會如何分配?

告訴你,這個情況肯定『分唔勻』,原因簡單,因為這裡共有 8 個『女士』A_i,但只可 7 個『男士』{1,2,3,4,5,7,8}『可供選擇』,七夫豈能配八妻?

更一般是,隨便找出 k 個『女士』,她們的對象數目,一定不能少於k,才可能『分得勻』。

用圖論或組合的術語,『分得勻』即是存在所謂『完美配合』(perfect matching)。

從上述討論,我們略略可見,若『存在完美配合』,則『隨便找出 k 個『女士』,她們的對象數目不少於 k』;逆向地,若『隨便找出 k 個『女士』,她們的對象數目不少於 k』,能不能保證『存在完美配合』?原來是可以的!這就是所謂何氏婚姻定理(Philip Hall’s marriage theorem),稍微數學化地表達:

Let A_i \subset \mathbb{N} (i = 1, 2, ..., n).
\exists distinct natural numbers k_i \in A_i iff
|A_{i_1}\cup A_{i_2}\cup \dots \cup A_{i_k}| \ge k (k = 1, 2, ..., n) with \{i_1, i_2, ..., i_k\} \subset \{1, 2, 3, ..., n\}

火星文?嗯,不太算吧。它所表達的,正是前段有關完美配合的內容而已。這裡只是數學『包裝』,但這個包裝不是用來唬人,而是真的有助證明時論述的方便。

起碼有三個方法證明婚姻定理,只介紹一個。

姑且稱 “|A_{i_1}\cup A_{i_2}\cup \dots \cup A_{i_k}| \ge k (k = 1, 2, ..., n) with \{i_1, i_2, ..., i_k\} \subset \{1, 2, 3, ..., n\}" 為何氏條件。

用 M.I.。

n = 1,由何氏條件,知 A_1 非空,即存在 k_1 \in A_1,即婚姻定理顯然成立。

假設當 n = m,婚姻定理仍然成立。
(注:我知我係 poor presentation,應寫 for any natural number m, suppose P(m) is true…,但,都係 skip 好了。)

考慮當 n = m + 1 的情況。

I = \{i_1, i_2, ..., i_k\} \subset \{1, 2, 3, ..., m + 1\}
A(I) = A_{i_1}\cup A_{i_2}\cup ... \cup A_{i_k}
由何氏條件,得 |A(I)| \ge |I|

(情況一)除 I = \PhiI = \{1, 2, 3, ..., m + 1\} 外,均有 |A(I)| > |I|

由何氏條件,知 A_{m + 1} 非空,可取 k_{m + 1} \in A_{m + 1}。現在把這個 k_{m + 1} 在之前的 mA_i 內『除去』,即設 B_i = A_i \backslash \{k_{m + 1}\} (i = 1, 2, ..., m)。現在看看這 mB_i 是否一樣滿足何氏條件。

對任何非空集 I \subset \{1, 2, ..., m\}|B(I)| \ge |A(I)| - 1。(想想 B_iA_i 差了什麼。)

由(情況一)假設,知 |B(I)| > |I| - 1,即 |B(I)| \ge |I|,可見集族 \{B_1, B_2, ..., B_m\} 也符合何氏條件。由 M.I. assumption,存在相異的自然數 k_i \in B_i,亦即存在自然數 k_i \in A_i (i = 1, 2, ..., m + 1)

(情況二)在 \{1, 2, 3, ..., m + 1\} 中存在真子集 I,使 |A(I)| = |I|

由 M.I. assumption,存在相異自然數 k_i \in A_i (i \in I)

考慮 J = \{1, 2, ..., m + 1\} \backslash I,命 C_j = A_j \backslash A(I) (j \in J)

好了,現在看看 C_j 是否符合何氏條件。

C(J) = C(I \cup J) \backslash C(I),故

|C(J)| = |C(I \cup J)| - |C(I)| \ge |I \cup J| - |I| = |J|

即集族 \{C_j\}_{j\in J} 符合何氏條件。故由 M.I. assumption,即存在相異自然數 k_j \in C_j (j \in J),亦即是說存在 k_i \in A_i (i \in \{1, 2, ..., m + 1\})

還有另一個來自雷多(Rado)的證法。精采呢,還有更多有趣的東西,有興趣可看看張鎮華教授寫的《相異代表系古今談》

http://episte.math.ntu.edu.tw/articles/mm/mm_10_1_09/index.html

發表迴響 »

仍無迴響。

RSS feed for comments on this post. TrackBack URI

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 變更 )

Twitter picture

You are commenting using your Twitter account. Log Out / 變更 )

Facebook照片

You are commenting using your Facebook account. Log Out / 變更 )

Google+ photo

You are commenting using your Google+ account. Log Out / 變更 )

連結到 %s

在WordPress.com寫網誌.

%d 位部落客按了讚: