[repost ]离散数学之把妹要诀

original:http://ift.tt/1oXSH6k 离散数学课（CSCI 2110）上，讲到一个有趣的问题。 假设有五个男生，五个女生，每个人都在自己心中对五个异性有一定的 preference 排序，比如： 以上的排序表解读为：男生 1 最中意女生C，次中意女生B，次次中意女生E…… 以此类推…… 在五男五女全部成功脱光之后（假设都在圈子内部解决），定义一个 unstable matching 为：如果存在一对不是情侣的男女符合以下情况： 对于该男，该女在他的 preference 列表中处于现任女友的前面，对于该女，该男在他的 preference 列表中亦处于现任男友的前面，那么这对男女必然有私奔的倾向…… 这样的情景即为 unstable matching。反之，若不存在这样一对有私奔倾向的男女，即为 stable matching。 问题是：是否在任何情况下，即不论各位的 preference 列表如何变化，只要男女数量相同，总是存在一个 stable matching。 （当然，搅基之类的，是不可以的……） 在上面五男五女的例子里，一种 stable matching 如下： 因为每个女生最中意的男生都不同，所以只要让女生们都选择跟自己最中意的男生在一起，她们就都不会有和其他男生私奔的想法。虽然男生们会表示略苦逼啊！仍然不失为一个 stable matching……。 那么如果有n男n女，每个人心中都已经有了一个 preference 列表，stable matching 是不是一定存在呢？ 1962 年，Gale 和 Shapley 证明了 stable matching 是一定存在的。 首先他们给出了一个算法： 第一天早上：所有男生都向自己最中意的女生表白。 第一天中午：每个女生都被表白了n次（可能是 0 次）之后，拒绝了相对不太中意的那n-1 […]



via WordPress http://ift.tt/1vX2IXn