下表包含了十個人(五男五女)他們心目中的理想對象排名。如果你是媒人的話,你會把怎麼把他們湊成五對,並且保證這十個人婚後不會外遇呢?又,外遇只會發生在當你安排了

A 女 和 M 男 結婚
B 女 和 K 男 結婚

由下表可知, A 喜歡 K 多於 M,K 也喜歡 A 多於 B,所以 A 和 K 就會背著 M 和 B 外遇啦。

《 作答時間:5分鐘 》

女生心中的排名   男生心中排名

Ann

J > K > L > M > N

 
John

E > B > D > C > A


Betty

M > K > L > N > J

 
Ken

A > B > D > C > E


Cindy

J > L > N > K > M

 
Lewis

D > B > E > A > C


Doris

M > N > L > K > J

 
Manning

E > D > C > B > A


Eva

K > N > L > J > M

 
Neo

C > D > A > B > E




找到答案了沒?





什麼,你沒有算一直往下看?



好啦,告訴你答案,這個題目的答案其實不只一組,下面列出兩組答案,也可能有其他的答案。

Ans1
Ann - Ken

Betty - Lewis

Cindy - Neo

Doris - Manning

Eva - John
Ans2
Ann - Ken

Betty - Lewis

Cindy - John

Doris - Manning

Eva - Neo

這兩個答案差別在 Cindy, Eva, John, 和 Neo 交換了配對。

下一個問題來啦,如果你是 John,你希望是那個答案呢?

讓我們再看一次 John 心目中的排名,會發現在第一個答案裡,他娶了最愛的 Eva,但是在第二個答案裡,他卻娶到他有點不愛的 Cindy。


John

E > B > D > C > A


再看Cindy的例子,第一個答案裡她要嫁給她覺得普通的 Neo,第二個答案裡她卻嫁給了最愛的 John 。


Cindy

J > L > N > K > M


所以,在這個題目裡聰明人會去賄賂媒人喲。

但是,媒人的影響力早就趨近於零啦,男生有喜歡的女生當然要勇敢去追啊。噹噹噹,第三題來了!

在男生可以追女生的情況下,這個問題要怎麼解呢?

別煩惱,神奇的數學家已經研究過這個問題啦,這個問題叫做 stable marriage problem (穩定婚配問題)。

他們提出來的算法是這樣的:

1. 每天早上男生向最心儀的女生表白。
2. 每天下午女生在收到零到多個男生的表白後,選擇繼續和其中她最喜歡的男生保持曖昧,然後其餘的男生會收到好人卡。
3. 每天晚上,收到好人卡的男生把這個女生從他的名單中劃掉。
4. 重覆 1-3 步驟直到所有的男生都沒有收到好人卡。

按照這個算法計算會得到結果如下(名字上有中橫劃的表示他收到了好人卡,像是第一天的 Manning 和第二天的 Lewis),在第三天沒有任何人收到好人卡了,所以得到 A-K, B-L, C-N, D-M, E-J 的答案。再仔細的看一看,這個答案是 Ans1 嘛,就是對 John 來說很棒,對Cindy 來說不怎麼好的答案。

 
Ann

Betty

Cindy

Doris

Eva
第一天
Ken
 
Neo

Lewis

John , Manning
第二天
Ken
 
Neo

Lewis, Manning

John
第三天
Ken

Lewis

Neo

Manning

John



你以為這堂數學課要下課了嗎?NO. 我們現在都可以公投了耶,你以為女生還在傻傻地等男生來追嗎?

第四題,男生太宅,所有的女生決定由她們採取主動,這樣答案會是什麼呢?

這一題很簡單吧,就把男女生的角色對調重新跑一次演算法就行了。

這樣算出來的結果會是 Ans2,就是 Cindy 喜歡,但是 John 不喜歡的答案。

 
John

Ken

Lewis

Manning

Neo
第一天
Ann, Cindy

Eva
 
  Betty,   Doris
 
第二天
Cindy

Eva,      Ann,    Betty
 
Doris
 
第三天
Cindy

Ann

Betty

Doris

Eva


你發現這中間的規律了嗎?男追女,得到Ans1 ,結果對男生比較好,女追男,得到Ans2 ,結果對女生比較好。主動追求的一方雖然會被拒絕,感覺起來比較可憐,可是事實上, 不主動的那一方才是真正倒楣的,因為他們雖然能發發卡,但是也只能就追求者中選擇,當追求者都不是那麼中意的時候也只好從中挑一個比較不爛的。

當然,現實生活比單純化了的數學題要複雜許多,尤其是現在男可追女、女可追男、男男、女女還有很多不及備載,我也不知道數學家該怎麼辦。但是我保證大部份的人都曾經用過本文裡介紹的演算法,想想看,是什麼時候用到的?提示:這個演算法是用在配對上面的。嘿嘿,就是聯考分發大家上那個科系的時候,也應該是用這個算法喔,而且因為是考生填寫志願,所以考生是佔了能夠最佳化的那一方。


PS:親愛的艾底迪,這篇文章是為你寫的喲。

PS2:感謝咩咩叫Mei 讓我用他的圖(可愛的黃色couple就是從他那裡來的)。其他的娃娃是我用 Mii Editor 畫的,寫這篇文章好像在作美勞,好好玩。
創作者介紹

iron.snow.ball

ironsnow 發表在 痞客邦 PIXNET 留言(9) 人氣()


留言列表 (9)

發表留言
  • wawa
  • 真有趣

    真實人生如果也可以這樣計算就簡單多了(可能也比較無趣就是了~)

    原來是用Mii Editor畫的啊,怪不得覺得和Mii同個調子!:D
  • 最厲害的是數學可以用在思考現實生活裡複雜的問題耶,雖然是簡化再簡化了,但還是解答了一小部份的情形哩。

    Mii Editor 真的蠻好玩的,正考慮把我的 avatar 換一下。

    ironsnow 於 2008/01/05 04:38 回覆

  • Jessie
  • 哈,真的好可愛喔!我最近越來越覺得女生主動很好啊,這樣才能掌握主控權,選到自己比較喜歡的。被動的話,有一點冒險,誰知道喜歡的人會不會跑來追求呢?
  • 是低。我那時候學到這個,第一個想法就是,這一定要讓其他女生知道啊。

    ironsnow 於 2008/01/06 16:18 回覆

  • Ariel
  • 有一種追求方式叫做被動式的主動, 適合所有害羞的女生; 但是男生還是要放膽勇敢地追求, 101次求婚裡的男主角就是熟知上述數學的最好的典範!
    艾底笛! 衝阿. 讓會"飛"的也不飛吧 :P
  • 什麼是被動式主動啊?美女Ariel快點教我們吧。

    還有你看艾底笛說要來留言到現在還沒來留,這是要怎麼衝哩?傷腦筋。

    ironsnow 於 2008/01/06 16:18 回覆

  • ys
  • 問個白癡問題 (可能我不夠仔細閱讀)
    附上的stable marriage problem 連結最後提到一堆game theory的各種"game" 請問stable marriage problem 和game theory 之間的關連?
  • Game theory 泛指所有研究「多於一個玩家時的策略性互動」(strategic interactions between agents)。

    根據 game 的性質,又可以分成 cooperative games 跟 non-cooperative games。這篇文章講的 stable marriage problem 是 cooperative games 的一個例子。

    一般我們比較熟悉的 game,像是下棋、或是 prisoner's dilemma,則是 non-cooperative games。電影A Beautiful Mind 有演過的 Nash,他的貢獻 Nash equilibrium 主要也是在研究 non-cooperative games。

    ironsnow 於 2008/01/07 01:46 回覆

  • Green
  • 艾底迪應該把它貼在床頭前,每日早晚三餐外加點心時間默背....
    可能....十年後會有進步Orz
    衝吧!!!艾底迪~~~~
    (吾人乃"皇帝不急急死太監"之類?!)
  • 對啊小綠,我看我們得設計個十日特訓之類的。

    ironsnow 於 2008/01/09 02:22 回覆

  • ys
  • nash equilibrium我知道 以前學microeconomic theory學到 事實上還有分是兩方同時進行還是一方先進行完然後另一方再進行等等各種game

    不過我還是不大清楚 怎麼說stable marriage problem是cooperative games呢 ?如果兩方的利益不同,應該沒有合作的動機吧! 還是我對cooperative的定義根本混淆了!改天看你上線再跟你討教一下
  • 這是 wiki 上的定義:

    A cooperative game is a game where groups of players ("coalitions") may enforce cooperative behaviour, hence the game is a competition between coalitions of players, rather than between individual players.

    ironsnow 於 2008/01/09 02:18 回覆

  • Seeh
  • 加上規則

    我想到現實世界,就是被發好人卡後就要停止追求該對象休息一回合,最心儀的對象如果沒表示,下一回合就要降三級。

    還有個數學理論是選妃理論,或是撿石頭原理,王子到鄰國作客,國王分別請三個女兒一個一個出場,當下就要決定要或是換下一位,機率上是放掉第一位,第二位如果比第一位優就答應,不然就選第三位。走在路上撿石頭,只能選一次,走過的路不能回頭,要怎麼選到較大顆的石頭?
  • 怎麼又有考試 >.<

    我猜撿石頭的策略是用前面一半的路當成 training examples, 了解自己該接受的好石頭範圍,在後面一半的路只要一看到符合的就撿起來。不知道對不對呢?

    ironsnow 於 2008/01/18 15:42 回覆

  • gulgula
  • 越來越猛

    xavier果然是提問大師
  • 沒錯

    ironsnow 於 2008/01/18 15:43 回覆