追爱的数学模型

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