close
下表包含了十個人（五男五女）他們心目中的理想對象排名。如果你是媒人的話，你會把怎麼把他們湊成五對，並且保證這十個人婚後不會外遇呢？又，外遇只會發生在當你安排了
A 女 和 M 男 結婚
B 女 和 K 男 結婚
由下表可知， A 喜歡 K 多於 M，K 也喜歡 A 多於 B，所以 A 和 K 就會背著 M 和 B 外遇啦。
《 作答時間：5分鐘 》
找到答案了沒？
什麼，你沒有算一直往下看？
好啦，告訴你答案，這個題目的答案其實不只一組，下面列出兩組答案，也可能有其他的答案。
這兩個答案差別在 Cindy, Eva, John, 和 Neo 交換了配對。
下一個問題來啦，如果你是 John，你希望是那個答案呢？
讓我們再看一次 John 心目中的排名，會發現在第一個答案裡，他娶了最愛的 Eva，但是在第二個答案裡，他卻娶到他有點不愛的 Cindy。
再看Cindy的例子，第一個答案裡她要嫁給她覺得普通的 Neo，第二個答案裡她卻嫁給了最愛的 John 。
所以，在這個題目裡聰明人會去賄賂媒人喲。
但是，媒人的影響力早就趨近於零啦，男生有喜歡的女生當然要勇敢去追啊。噹噹噹，第三題來了！
在男生可以追女生的情況下，這個問題要怎麼解呢？
別煩惱，神奇的數學家已經研究過這個問題啦，這個問題叫做 stable marriage problem （穩定婚配問題）。
他們提出來的算法是這樣的：
1. 每天早上男生向最心儀的女生表白。
2. 每天下午女生在收到零到多個男生的表白後，選擇繼續和其中她最喜歡的男生保持曖昧，然後其餘的男生會收到好人卡。
3. 每天晚上，收到好人卡的男生把這個女生從他的名單中劃掉。
4. 重覆 1-3 步驟直到所有的男生都沒有收到好人卡。
按照這個算法計算會得到結果如下（名字上有中橫劃的表示他收到了好人卡，像是第一天的 Manning 和第二天的 Lewis），在第三天沒有任何人收到好人卡了，所以得到 A-K, B-L, C-N, D-M, E-J 的答案。再仔細的看一看，這個答案是 Ans1 嘛，就是對 John 來說很棒，對Cindy 來說不怎麼好的答案。
你以為這堂數學課要下課了嗎？NO. 我們現在都可以公投了耶，你以為女生還在傻傻地等男生來追嗎？
第四題，男生太宅，所有的女生決定由她們採取主動，這樣答案會是什麼呢？
這一題很簡單吧，就把男女生的角色對調重新跑一次演算法就行了。
這樣算出來的結果會是 Ans2，就是 Cindy 喜歡，但是 John 不喜歡的答案。
你發現這中間的規律了嗎？男追女，得到Ans1 ，結果對男生比較好，女追男，得到Ans2 ，結果對女生比較好。主動追求的一方雖然會被拒絕，感覺起來比較可憐，可是事實上， 不主動的那一方才是真正倒楣的，因為他們雖然能發發卡，但是也只能就追求者中選擇，當追求者都不是那麼中意的時候也只好從中挑一個比較不爛的。
當然，現實生活比單純化了的數學題要複雜許多，尤其是現在男可追女、女可追男、男男、女女還有很多不及備載，我也不知道數學家該怎麼辦。但是我保證大部份的人都曾經用過本文裡介紹的演算法，想想看，是什麼時候用到的？提示：這個演算法是用在配對上面的。嘿嘿，就是聯考分發大家上那個科系的時候，也應該是用這個算法喔，而且因為是考生填寫志願，所以考生是佔了能夠最佳化的那一方。
PS：親愛的艾底迪，這篇文章是為你寫的喲。
PS2：感謝咩咩叫Mei 讓我用他的圖（可愛的黃色couple就是從他那裡來的）。其他的娃娃是我用 Mii Editor 畫的，寫這篇文章好像在作美勞，好好玩。
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 , | |
| 第二天 | Ken | Neo | | John | |
| 第三天 | Ken | Lewis | Neo | Manning | John |
你以為這堂數學課要下課了嗎？NO. 我們現在都可以公投了耶，你以為女生還在傻傻地等男生來追嗎？
第四題，男生太宅，所有的女生決定由她們採取主動，這樣答案會是什麼呢？
這一題很簡單吧，就把男女生的角色對調重新跑一次演算法就行了。
這樣算出來的結果會是 Ans2，就是 Cindy 喜歡，但是 John 不喜歡的答案。
John | Ken | Lewis | Manning | Neo | |
| 第一天 | | Eva | | ||
| 第二天 | Cindy | | Doris | ||
| 第三天 | Cindy | Ann | Betty | Doris | Eva |
你發現這中間的規律了嗎？男追女，得到Ans1 ，結果對男生比較好，女追男，得到Ans2 ，結果對女生比較好。主動追求的一方雖然會被拒絕，感覺起來比較可憐，可是事實上， 不主動的那一方才是真正倒楣的，因為他們雖然能發發卡，但是也只能就追求者中選擇，當追求者都不是那麼中意的時候也只好從中挑一個比較不爛的。
當然，現實生活比單純化了的數學題要複雜許多，尤其是現在男可追女、女可追男、男男、女女還有很多不及備載，我也不知道數學家該怎麼辦。但是我保證大部份的人都曾經用過本文裡介紹的演算法，想想看，是什麼時候用到的？提示：這個演算法是用在配對上面的。嘿嘿，就是聯考分發大家上那個科系的時候，也應該是用這個算法喔，而且因為是考生填寫志願，所以考生是佔了能夠最佳化的那一方。
PS：親愛的艾底迪，這篇文章是為你寫的喲。
PS2：感謝咩咩叫Mei 讓我用他的圖（可愛的黃色couple就是從他那裡來的）。其他的娃娃是我用 Mii Editor 畫的，寫這篇文章好像在作美勞，好好玩。
全站熱搜
留言列表
