iron．snow．ball

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

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

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 畫的，寫這篇文章好像在作美勞，好好玩。