2008 (4)
说的是某位帅哥,手头有一叠美人的照片,想从中挑一个白雪公主。他把照片一字排开,一个个都如花似玉,难以取舍。于是随机给照片排了个顺序,决定依顺序相亲。他要凭自己的智慧给各位打分,得分最高的就是那位白雪公主了。他也知道,那些美女一个个心高气傲,如果相亲没有被当场选中,再返回找她是没有希望的。也就是说,如果他没有当场接受某位,他就永远失去了她,即便后来经过比较发现她才是真正的白雪公主。当然,如果他已接受某亮女为白雪公主,以后的相亲就可停止了。为了简化问题,我们总假设各自得分不一样。
如何才能选上真正的白雪公主呢?
自然,在这样的条件下,没有人有绝对把握保证找到白雪公主,所能做的就是使找到的概率尽可能大。比如,当场接受第一位,她是白雪公主的概率仅是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。
好了,各位帅哥亮妹可以依计而行。
祝各位运交桃花!
蓝天谬夸。我只是想把一些数学问题说的有趣一点而已。谢蓝天的鼓舞,争取多写点!
谢楼主谬夸。谢楼主来访。
太佩服了!有这种才能不用相亲也会有美女追啦 :))
冒泡感谢博主的《趣味数学》系列,真正好东西,受益匪浅。