趣味数学（六） 相亲的技巧

说的是某位帅哥，手头有一叠美人的照片，想从中挑一个白雪公主。他把照片一字排开，一个个都如花似玉，难以取舍。于是随机给照片排了个顺序，决定依顺序相亲。他要凭自己的智慧给各位打分，得分最高的就是那位白雪公主了。他也知道，那些美女一个个心高气傲，如果相亲没有被当场选中，再返回找她是没有希望的。也就是说，如果他没有当场接受某位，他就永远失去了她，即便后来经过比较发现她才是真正的白雪公主。当然，如果他已接受某亮女为白雪公主，以后的相亲就可停止了。为了简化问题，我们总假设各自得分不一样。

如何才能选上真正的白雪公主呢？

自然，在这样的条件下，没有人有绝对把握保证找到白雪公主，所能做的就是使找到的概率尽可能大。比如，当场接受第一位，她是白雪公主的概率仅是1/N。

有办法让挑中白雪公主的概率变得更大些吗？

假设总共有N位美人。N=1时，别无选择，就是她了。N=2时，选择也不多，能选中的概率就是1/2。

N=3时，能做得比1/3更好吗？

能！一定能！大家先想一秒钟。

具体做法如下：先拒绝第一位，接着相亲。遇到比第一位好的就当场接受。

这时能选中的概率又是多少？

假设三位亮女得分分别是X，Y，Z并且假设X最小，Y次之，Z最大。不难列出总共有6种可能的排法：XYZ，XZY，YXZ，YZX，ZXY，ZYX。按我们的方案，选中得分最高的情形是XZY，YZX和YXZ，所以选中的概率是3/6=1/2。

N=4时，有如下两种方案：

方案1：先拒绝第一位，接着相亲。遇到比第一位好的就当场接受。
方案2：先拒绝前两位，接着相亲。遇到比两位都好的就当场接受。

让我们算算两种方案的概率。

为方便起见，不妨把四位的得分计成1，2，3，4。(注意，仅是为了方便我们假设得分为1，2，3，4。其实也可能是1.01，1.02， 1.1，1.2。要不然，尽可以等到得分为4的那位了。) 我们先列出所有24种可能的排法：
1234，1243，1324，1342，1423，1432，2134，2143，2314，2341，2413，2431，3124，3142，3214，3241，3412，3421，4123，4132，4213，4231，4312，4321。

按方案1，下列情形能选上白雪公主（得分为4的那位）：1423，1432，2413，2431，3412，3421，2143，3142，3241，3124，3214。所以方案1选中的概率是11/24。

按方案2，下列情形能选上白雪公主：1243，2143，1342，3142，2341，3241，1324，2314，3124，3214。所以方案2选中的概率是10/24。

方案1的概率远好于1/4。

自然，N越大，选择越难。奇怪的是，不管N多大我们都有办法保证选中白雪公主的概率大于1/3。

聪明的读者也许已找到了办法，那么，恭喜你抱得美人归（或帅哥归）。

固定一个数K，我们的方案K就是：先拒绝前K位，接着相亲。遇到比K位都好的就当场接受。然后再选出最好的那个数K。

让我们接着探讨方案K选中白雪公主的概率P(K)。用B表示白雪公主，用B=I表示她被排在第I个位置，并用P(B|B=I)表示白雪公主排在I位并且被选上的条件概率。用条件概率求P(K)如下：P(K)=P(B=1)P(B|B=1)+P(B=2)P(B|B=2)+...+P(B=N)P(B|B=N)。根据假设，P(B=I)=1/N。所以又有：P(K)=(1/N){P(B|B=1)+P(B|B=2)+...+P(B|B=N)}。

按方案K，如果I小于或等于K，我们有P(B|B=I)=0。如果I大于K，如何计算P(B|B=I)呢？

先看一个例子。在N=4，K=2，I=4时，1234，2134都选不上白雪公主，因为都把得分为3的选上了。所以要在B排在第I个位置上时还能选上B，前I-1个中的最高分必需出现在前K个位置中。也就是：P(B|B=I)=K/（I-1），从而
P(K)　=　(1/N){P(B|B=K+1)　+　P(B|B=K+2)　+　...　+　P(B|B=N)}
　　　=　(K/N){1/K　+　1/(K+1)　+　...　+　1/(N-1)}。

通过简单的数学计算，P(K)约等于(K/N)log(N/K)，这里的对数是自然对数，以e为底。其中e约等于2.71828。如果让K等于N/e的整数部分，P(K)就约等于1/e。注意1/e约等于0.36788，比1/3大。如果N=100，可选K=36或K=37。

好了，各位帅哥亮妹可以依计而行。

祝各位运交桃花！
 

请阅读更多我的博客文章>>>