,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,数学建模素养,意识篇之,追爱的数学模型,主讲教师 高全胜教授,主讲教师 高全胜教授,1.,数模女汉子选择追求者问题,虽然是数模女汉子，但对找到自己心中的白马王子，渴望和普通女生一样的浪漫，找到自己一生的幸福是每个人的追求。,但是面对追求者们，女生应该是选择还是拒绝，她的策略是社么？,怎样才能以最大的可能找到自己的“理想的他”呢？,1.数模女汉子选择追求者问题 虽然是数模女汉子，但对找到自己,1.1.,问题简化,假设一个女生想在一段时间中和一位男生开始一段感情，并且在这段时间中有,N,个男生追求这位女生。,这,N,个男生是以不同的先后顺序来追求这位女生。,在适合这个女生的意义上，假设追求者中任何两个男生都是可以比较的，而且没有相等的情况。,这样我们对这,N,个男生从,1,到,N,进行编号，其中数字越大表示越适合这个女生。这样在这段时间中，女生的,Mr.Right,就是男生,N,了。,现在问题变成,面对这,N,个追求者，应该以怎样的策略才能使得在第一次选择接受的男生就是,N,的可能性最大。,1.1.问题简化假设一个女生想在一段时间中和一位男生开始一段,1.2.,模型假设,1,、,N,个男生以不同的先后顺序向女生表白，即在任一时刻不存在两个或两个以上的男生向这位女生表白的情况的发生，而且任何一种顺序都是完全等概率的。,2,、面对表白后的男生，女生只能做出接受和拒绝两种选择，不存在暧昧或者其它选择。,3,、任一时刻，女生最多只能和一位男生谈恋爱，不存在脚踏多船的情况。,4,、已经被拒绝的男生不会再次追求这位女生。,1.2.模型假设 1、N 个男生以不同的先后顺序向女生表白，,1.3.,问题分析,简单策略：如果一旦有男生向女生表白，女生就选择接受。这种策略下显然女生以,1/N,的概率找到自己的,Mr.Right,。当,N,比较大的时候，这个概率就很小了，显然这种策略不是最优的。,复杂策略：对于最先表白的,M,个人，无论女生感觉如何都选择拒绝；以后遇到男生向女生表白的情况，只要这个男生的编号比前面,M,个男生的编号都大，即这个男生比前面,M,个男生更适合女生，那么女生选择接受，否则选择拒绝。,1.3.问题分析简单策略：如果一旦有男生向女生表白，女生就选,以,N=3,为例,三个男生追求女生，共有六种排列方式：,1 2 3,；,1 3 2,；,2 1 3,；,2 3 1,；,3 1 2,；,3 2 1,。如果女生采用上述最简单的策略，那么只有最后两种排列方式选择到,Mr.Right,，概率为,2/3!=1/3,。,如果女生采用上面我们提出的策略，这里我们取,M=1,，即无论第一个人是否优秀，女生都选择拒绝。然后对于之后的追求者，只要他比第一个男生更适合女生就选择接受，否则拒绝。基于这种策略，“,1 3 2”,、“,2 1 3”,、“,2 3 1”,这三种排列顺序下女生都会在第一次做出接受的选择时遇到“,3”,，这样我们就把这种概率增大到,3/3!=1/2,。,现在我们的问题就归结为，,对于一般的,N,，什么样的,M,才会使这种概率达到最大值呢,？（在这种模型中，前面,M,个男生就被称为“炮灰垫背,”,，无论他们有多么优秀都要被拒绝）,以N=3 为例 三个男生追求女生，共有六种排列方式：1 2,1.4.,模型建立,在这一部分中，根据上面的模型假设，我们先找到对于给定的,M,和,N(1MN),，女生选择到,Mr.Right,的概率的表达式。,1,到,N,个数字进行排列共有,N!,种 可能。当数字,N,出现在第,P,位置（,MP0,In(1+x)0,时,In(1+x)x,。,所以由左不等式,所以M 应满足,所以：,当,N,比较大时，同理由右不等式可得,M N/e,，以上,e,为自然对数。若记,x,为不大于,x,的最大整数，由以上推导我们可猜测当,M,取,N/e,或,N/e+1,时，该表达式取得最大值。,所以：,1.6.,结果分析,由上述分析可以得到如下结论：为了使一个女生以最大的概率在第一次选择接受男生时遇到的正是,Mr.Right,，女生应该采用以下的策略：,拒绝前,M=N/e,或者,N/e+1,个追求者，当其后的追求者比前,M,个追求者更适合则接受，否则拒绝。,假设你一共会遇到大概,30,个，就应该拒绝掉前,30/e30/2.71811,个求爱者，然后从第,12,个求爱者开始，一旦发现比前面,11,个求爱者都好的人，就果断接受他。由于,1/e,大约等于,37%,，因此这条爱情大法也叫做,37%,法则。,不过，,37%,法则有一个小问题：如果最佳人选本来就在这,37%,的人里面，错过这,37%,的人之后，她就再也碰不上更好的了。,但在游戏过程中，她并不知道最佳人选已经被拒，因此她会一直痴痴地等待。也就是说，,MM,将会有,37%,的概率“失败退场”，或者以被迫选择最后一名求爱者的结局而告终,1.6.结果分析 由上述分析可以得到如下结论：为了使一个女生,37%,法则“实测”！,37%,法则的效果究竟如何呢？我们在计算机上编写程序模拟了当,n=30,时利用,37%,法则进行选择的过程（如果,MM,始终未接受求爱者，则自动选择最后一名求爱者）。编号越小的男生越次，编号为,30,的男生则表示最佳选择。程序运行,10000,次之后，竟然有大约,4000,次选中最佳男生，可见,37%,法则确实有效啊。,不知道了解此问题的女生，会不会多了一种分手的理由：不好意思，你是那,37%,的人,对于男生，该模型残酷的，指出了炮灰存在的现实意义，正如伟大哲学家萨特所说“存在即是合理”，炮灰的不可避免性也许是对已经和即将成为炮灰的男生的宽慰。,But,However,，,Whatsmore(*_*),，,该模型的量化指标都是采自女生主观臆断，各个指标的合理性希望广大,MM,慎思之。,37%法则“实测”！37%法则的效果究竟如何呢？我们在计,题外话,“打仗的时候，很多士兵身先士卒，跑到前线勇往直前。通常来说，走在最前面的，都会给大炮打中（古代的大炮像象个球一样滚过来的）成为灰烬。而后来的士兵，就踏着炮灰走到胜利，所以成为别人利益的牺牲品的人就叫炮灰,.,。”,-,百度上关于炮灰的解释,在本篇文章中介绍的“炮灰模型”中，前,M,个男生就成了炮灰的角色，无论其有多么优秀，都会被拒绝。,朋友，如果你追求一个女生而遭到拒绝，看完这篇文章后你会突然发现，也许这不是你的的错，也许你真的很优秀，只是很不幸，你成了“炮灰”。,希望上面这些看似复杂的推导和模型对你能有所启发。不要因为一次的拒绝而伤心、失落，振作起来，你的,Miss Right is waiting for you somewhere!,题外话“打仗的时候，很多士兵身先士卒，跑到前线勇往直前。通常,进一步的解释,再由前面的理论小推论一下：设女性最为灿烂的青春为,18-28,岁，在这段时间中将会遇到一生中几乎全部的追求者（之前之后的忽略不计），且追求者均匀分布,(,每年一个），则女性从,18+10/e=21.7,即,22,岁左右开始接受追求,这告诉我们，想谈恋爱找大四的（不现实，但可能会符合婚姻法）,进一步的解释,1.7.,模型的扩展,微软钻石面试题：一楼到十楼的每层电梯门口都放着一颗钻石，钻石大小不一。你乘坐电梯从一楼到十楼，每层楼电梯门都会打开一次，只能拿一次钻石，问怎样才能拿到最大的一颗？,我们可以把每个钻石看做是前来表白的男生，,MM,坐电梯上楼对其进行选择，这样该问题就可以化为,MM,选择最佳追求者的问题了。即有,10,个追求者，要求,MM,拒掉的男生的人数,M,为多少时，才可以以最大概率找到,Mr.Right,？,1.7.1,微软钻石面试题,1.7.模型的扩展微软钻石面试题：一楼到十楼的每层电梯门口都,仿真结果,将,N=10,代入前面的结论的表达式，由于是离散化的且,N,不是很大，我们可以用遍历搜素进行求值，当然本问题用手工计算或计算器计算下就好了。经过计算可知,M=3,。,那么对于较大的,N,，我们给出,MATLAB,的结果：仿真后可得随着,N,的增长，按此方案选择最优值在,1/e,附近。,结论：因此对于微软钻石选择问题的策略是：前,3,层都不拿钻石，并记录下最大的钻石的大小，然后从第四层开始，只要遇到比前三层都大的钻石就拿。,仿真结果将N=10代入前面的结论的表达式，由于是离散化的且N,1.7.2,非诚勿扰问题,在每期,非诚勿扰,节目上，面对一位位男嘉宾，,24,位单身女生要做出不止一次“艰难的决定”：到底要不要继续亮灯？把灯灭掉意味着放弃了这一次机会，继续亮灯则有可能结束节目之旅，放弃了未来更多的选择。,怎么办？去向,非诚勿扰,的黄菡老师和乐嘉老师请教一下？其实你还可以向欧拉老师请教一下。你没听错。大数学家欧拉对一个神秘的数学常数,e 2.718,深有研究，这个数字和“拒人问题”竟然有着直接的联系。,为了便于我们分析，让我们把生活中各种复杂纠纷的恋爱故事抽象成一个简单的数学过程。假设根据过去的经验，,MM,可以确定出今后将会遇到的男生个数，比如说,15,个、,30,个或者,50,个。不妨把男生的总人数设为,n,。这,n,个男生将会以一个随机的顺序排着队依次前来表白。每次被表白后，,MM,都只有两种选择：接受这个男生，结束这场“征婚游戏”，和他永远幸福地生活在一起；或者拒绝这个男生，继续考虑下一个表白者。我们不考虑,MM,脚踏两只船的情况，也不考虑和被拒男生破镜重圆的可能。最后，男人有好有坏，我们不妨假设,MM,心里会给男生们的优劣排出个名次来。,1.7.2 非诚勿扰问题在每期非诚勿扰节目上，面对一位位,聪明的,MM,会想到一个好办法：先和前面几个男生玩玩，试试水深；大致摸清了男生们的底细后，再开始认真考虑，和第一个比之前所有人都要好的男生发展关系。,从数学模型上说，就是先拒掉前面,k,个人，不管这些人有多好；然后从第,k+1,个人开始，一旦看到比之前所有人都要好的人，就毫不犹豫地选择他。不难看出，,k,的取值很讲究，太小了达不到试的效果，太大了又会导致真正可选的余地不多了。这就变成了一个纯数学问题：在男生总数,n,已知的情况下，当,k,等于何值时，按上述策略选中最佳男生的概率最大？,如果你预计求爱者有,n,个人，你应该先拒绝掉前,n/e,个人，静候下一个比这些人都好的人。,聪明的 MM 会想到一个好办法：先和前面几个男生玩玩，试试水,2.,数学博士的交友战略,克里斯,麦金利（,Chris McKinlay,）最近两件事：,（,1,）,忙博士论文,大规模数据处理和并行数值方法,；,（,2,）自从九个月前跟前女友分手之后，他就一直都在寻找新恋情，但迄今为止都是徒劳无果。,世纪佳缘，人人网,2.数学博士的交友战略克里斯麦金利（Chris McKin,2.1.,婚恋网站,OkCupid,是哈佛大学数学专业的学生在,2004,年创建的，它最初吸引用户的地方是可以使用算法来匹配会员。,流程：,会员需要做大量的多项选择题,，这些问题涵盖了包括政治、宗教、家庭、爱、性、智能手机在内的方方面面。比如：“以下哪项最有可能吸引你去看一部电影？”（爱情片、战争片、间谍片。）“宗教或神对你的,生命,有多重要？”（宗教冲突）,问题总共有数千个之多。平均而言，一个用户会挑选其中,350,个问题来回答，并用打分的方式说明这个问题对自己有多么重要：,0,代表“不重要”，,5,代表“必不可少”。,然后,OkCupid,的匹配引擎就会使用这些数据来,计算两个人的匹配度,。百分