趣味數學（六）相親的技巧

來源: 朝霞滿天於 2013-04-08 11:14:51 [檔案] [博客] [舊帖] [給我悄悄話] 本文已被閱讀：次 (4300 bytes)

說的是某位帥哥，手頭有一疊美人的照片，想從中挑一個白雪公主。他把照片一字排開，一個個都如花似玉，難以取舍。於是隨機給照片排了個順序，決定依順序相親。他要憑自己的智慧給各位打分，得分最高的就是那位白雪公主了。他也知道，那些美女一個個心高氣傲，如果相親沒有被當場選中，再返回找她是沒有希望的。也就是說，如果他沒有當場接受某位，他就永遠失去了她，即便後來經過比較發現她才是真正的白雪公主。當然，如果他已接受某亮女為白雪公主，以後的相親就可停止了。為了簡化問題，我們總假設各自得分不一樣。

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

自然，在這樣的條件下，沒有人有絕對把握保證找到白雪公主，所能做的就是使找到的概率盡可能大。比如，當場接受第一位，她是白雪公主的概率僅是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。

好了，各位帥哥亮妹可以依計而行。

祝各位運交桃花！