你是否也有一个舍友,
终日陷于感情波动中不得脱身。
亦或自己曾几何时爱过一个人,
但最终还是各奔东西。
你是否曾怀疑过生活,
疑惑着是否有人能与自己相伴终身?
1962年,Gale和Shapelyz的研究成果表明:
世界上的所有人
都可以有相伴终生的伴侣。
是不是瞬间感觉未来充满光明!
下面很长一段文字跳过也可以告诉你如何为每个人找到适合自己,可以相伴终生的伴侣:
很长一段文字开始的地方
为了说明如何找到适合自己相伴终生的伴侣,让我们先来看一个简单的例子。
假设:
i)世界上的男孩子只会喜欢女孩子;
ii)世界上的女孩子只会喜欢男孩子;
iii)世界上的男孩子都会喜欢女孩子;
iv)世界上的女孩子都会喜欢男孩子;
v)每个人对任意两名异性能做出更希望与哪一位交往的判断;
vi)世界上所有人之间的喜欢程度可以比较,且不会舍弃现有的男(女)朋友跟自己不那么喜欢的人在一起;
vii)世界上男人和女人数相同且可数,设为n.
可以看到,这个例子中,为了简化问题,我们进行了非常苛刻的假设,下面我们建立在这样的假设下,说明条件强化的可测人必有可以相伴终生的伴侣定理,为了叙述方便,我们将用“稳定”这个词来代替“相伴终生”的关系。
如何定义稳定(相伴终生):
考虑这样的情形,现在有两对情侣B1,G1;B2,G2;如果B1和G2相比现在的伴侣都认为更愿意与对方交往的话。(也就是B1相比G1更喜欢G2;G2觉得相比B2更喜欢B1),则B1,G2就会甩掉当前伴侣,两人一起“私奔”。这样的情形我们称之为不稳定的。
如果某种情况下任意两对情侣不存在以上情形,
我们称之为这是一个稳定的情形。
根据我们以上的假设和定义,
我们可以构想这样一个情形:
一张长桌,
世界上所有的女生坐在一边,
世界上所有男生坐在另一边。
每个男生根据自己的判断
将对面的女生按交往意愿从大到小排序;
女生同样给男生排序。
下面 是一个人人安心的世界必然存在的构造性证明 我们着手创造一个“人人安心”的世界。
▲伪代码
1. 所有的男生向自己列表中首位女生表白。
2. 女生接收到男生的表白后将除了在自己名单中排名最靠前的一位男生之外的拒绝。
3. 循环得到某次没有任何一个男生被拒绝的情形
3.1 被拒绝的男生再次向列表中未被拒绝的排名最靠前的女生表白。
3.2 接受到申请的女生在之前表白中保留的(或有一位或没有)和新表白的男生(若干)中将除了在自己名单中排名最高的一位男生之外的男生拒绝。
4. 女生和最终保留(自己接受)的那个男生交往。
▲流程图:
▲算法实现:
这样得到的情形有以下两个特征:
(1)一定会使得所有人都能够配对成功。
证明:随着轮数的增加,总有一个时候所有人都能配上对。用反证法征明,男生根据自己心目中的排名依次对女生进行表白,假如有一个人没有配上对,那么这个人必定是向所有的女生进行表白了。但是女生只要被表白过一次,就不可能是单身,也就是说此时所有的女生都不是单身的,这与有一个人没有配上对是相悖的。所以假设不成立。
(2)最后得到的情况是稳定的。
随着轮数的增加,男生追求的对象越来越糟,而女生的男友则可能变得越来越好。假设男A和女1各有各自的对象,但是比起现在的对象,男A更喜欢女1,所以,在此之前男A肯定已经跟女1表白过的,并且女1拒绝了男A,也就是女1有了比男A更好的男友。证毕。
这里!后面认真看!
如果有上帝存在的话,
上帝知晓你对每一个人的喜欢程度
以上步骤完全可以由上帝执行
不需要经过表白拒绝的真实过程
换言之
我们可以找到一个
所有人都有相伴终生伴侣的世界。
然而现实远没有数学那么浪漫。
这种情形只是理论可能而已,
在现实生活中根本不可能操作。
然而
数学学院(珠海)学生会
在“数chedule”中发起活动
“缘觅”
把n确定为5
以分A,B组代替性别区分
用工作人员和程序代替上帝
化不可能为可能
只为将数学的魅力展现给大家
只为让大家在活动中
找到自己最合适的拍档
毕竟最合适的人互相督促
每天干活才更有动力!
是不是觉得数院的数chedule活动特别棒!
想不想给自己也来一次美丽的邂逅?
愿意的话
那就扫描下方二维码进入
我们的咨询群进一步了解吧!
不愿意的话,那就
再看一遍,直到愿意为止
咨询向左
报名转右
附 上文匹配算法详情请见
http://www.ams.org/publicoutreach/feature-column/fc-2015-03
文案丨数学学院(珠海)学生会
排版丨雨季风、地上兔
▼
▽
我们的故事
未完待续
二〇一八
马足龙沙
△
▲