上頁 1234 次頁

海外學人相親記 (第 2 頁)

李宗元

 

首頁 | 搜尋

.原載於數學傳播第二卷第三期
.作者當時任教於中央數學系

註釋
對外搜尋關鍵字
 
最佳的選擇

現在有 n 位閨秀,排好次序,一一出現君前。我已說過,我們假設她們各有不同的名次,(n 張卡片下所寫的獎金各有不同,最高獎為第一名,次高者第二名……)。我們以 xk 代表第 k 位閨秀的名次(或曰實際名次,即她在 n 位中算是老幾)。xk 是一個「亂動變數」(=「隨機變數」)。我也說過,她們每位的名次,你一無所知。你所知道的,是每位的臨時名次,也就是說,你看到第 k 位時,她在所看完的 k 位中,算是老幾。

前面的簡單辦法(「放棄前一半……」),結果已經非常不錯。因此我們自然地會想到更一般一點的辦法 3

Mr:放棄前面 k-1 位。自第 r 位起,首次遇到較前均佳者即停。

也就是說,自第 r 位起,選擇首次出現的臨時第一名。請注意,所謂放棄前面 r-1 位,當然是你決不選她們,(可憐的先鋒!),但是你仍應對她們每位打量一番,以便與後來的作個比較,也就是說,以便決定後來者的臨時名次。又 M1,沒有什麼意思:你必須選取第一位,因為第一位一定是一個臨時第一名。

我們規定一兩個符號,使下面的敘述方便些。令

P(Mr) 為根據上述辦法,選中第一名的機率
Sk 為根據上述辦法,第 k 位閨秀被選的事件

那麼(為什麼?)

\begin{displaymath}
P(M_r)=\sum^n_{k=r} P(S_k,x_k=1)=\sum^n_{k=r}\,P(S_k\vert x_k=1)P(x_k=1)
\end{displaymath} (1)

P(A,B) 代表 P(AB)。顯然, $P(x_k=1) = \frac{1}{n}$。(n 個不同數字亂排,最小的要在第 k 個位置)。至於 P(Sk|xk=1) 是什麼?假如第一名在第 k 個位置,那麼,按照 Mr,只有下面的情形我們才能選到她:這就是,前面 k-1 個數字(閨秀)中,最小的(最好的)要發生在最前面 r-1 個位置堙C(舉例說,r=3, k=6, 而各位閨秀的名次,依出場次序排,分別為 4,8,5,6,3,1,… 則按照 M3,我們必須選擇第五位,因為她是臨時第一名,所以真正的第一名就沒有被選到)。 顯然,上述事件的機會是 $\frac{(r-1)}{(k-1)}$,因此

\begin{displaymath}
P(M_r)=\frac{r-1}{n}\,\sum^{n}_{k=r}\,\frac{1}{k-1}\qquad r\geq 2
\end{displaymath} (2)

當然,以前已經說過,P(M1)=1/n

我們現在要檢查一下,在上述辦法堙A哪一個r能使P(Mr)最大。 把這個r叫做r*,那麼Mr*就是最佳的選擇法。看到這堙A 比較細心一點的讀者也許會問:你怎麼可以保證沒有再好的辦法呢?換句話說:最好的辦法,一定是在上述這類 $(M_r:r=2,3\cdots)$ 堶捷隉H 答案是肯定的,證明也不是很難;但是又要再費一番口舌,我想就算了罷。 讀者如要深究,可參照資料[4],[5],好好想一想。 4 我現在將 P(Mr) 簡寫作 f(r),以 $\triangle f(r)=f(r+1)-f(r)$ 代表 f(r) 的「增率」。從(2)式我們看到

\begin{displaymath}
\begin{eqalign}
\triangle f(r)= & \frac{r}{n}(\frac{1}{r}+\c...
...\
=&\frac{1}{n}(\sum^{n-1}_{k=r}\,\frac{1}{k}-1)
\end{eqalign}\end{displaymath} (3)



圖1

由這塈A可以注意到, $\triangle f(r)$r 增加而遞減。你又可以檢驗出, $\triangle f(2)>0$,(假設 n>4), $\triangle f(n-1)<0$。這表示當 r 增加時,f(r) 先增而後減,如圖1。 因此 r* 一定是首次使得 $\triangle f(r)\leq 0$ 的那個 r,也就是說, $\sum^{n-1}_{r^*}\,(\frac{1}{k})-1\leq 0$ 但是 $\sum^{n-1}_{r^*-1}(\frac{1}{k})-1>0$。所以 r* 滿足下面的式子

\begin{displaymath}
\frac{1}{r^*}+\cdots+\frac{1}{n-1}\leq 1< \frac{1}{r^*-1}+
\frac{1}{r^*}+\cdots+\frac{1}{n-1}
\end{displaymath} (4)

任意定了 n 後,r* 就可自(4)式中計算出來。

這埵魚鴘漪O,雖然 r*n 而變,但當 n 很大時,$\frac{r^*}{n}$ 幾乎沒有什麼變化。(事實上,實際的數據顯示,n=20 已經可算「很大」了)。怎樣看出這點來?這塈畯怑n提到「自然對數」$\log$。這是以 $e\approx2.718$ 為底的對數函數。 (有人將這 $\log$ 寫作 $\log_e$ 或者 $\ln$)。它是怎樣來的?最好的定義方法是: $\log{t}$ 是曲線 $y=\frac{1}{x}$x 軸在 x=1x=t 之間的面積,如圖2。這樣說的 話,e就是$\log {t}=1$的唯一的實數解。



圖2

如果我們比較面積,如圖3、圖4,你就可以看出

\begin{displaymath}
1+\frac{1}{2}+\cdots+\frac{1}{n-1}>\log{n}>\frac{1}{2}+\frac{1}{3}+\cdots+
\frac{1}{n}
\end{displaymath}



圖3



圖4


\begin{displaymath}
0<1+\frac{1}{2}+\cdots+\frac{1}{n-1}-\log{n}<1-\frac{1}{n}
\end{displaymath}

或者說
\begin{displaymath}
1+\frac{1}{2}+\cdots+\frac{1}{n-1}\approx\log{n}
\end{displaymath} (5)

兩者相差最多不超過1。(事實上當n增加時, $1+\frac{1}{2}+\cdots+\frac{1}{(n-1)}-\log{n}$會有一個極限,這個極限叫做尤拉Euler常數,其值約為0.5772)。

根據(5), $\frac{1}{r^*}+\cdots+\frac{1}{(n-1)}\approx\log{n}-\log{r^*}=\log{(\frac{n}{r^*})}$。 當n很大時,(4)式中左右兩邊相差無幾,(兩邊相差只一項。請注意(4)式的左邊顯示,當n很大時,r*也必很大),因此(4)式可以大約寫為

\begin{displaymath}
\log{\frac{n}{r^*}}\approx 1
\end{displaymath}

因為$\log{e}=1$,所以

\begin{displaymath}
r^*\approx \frac{n}{e} \approx 0.36n
\end{displaymath}

這時候的f(r*)大約是

\begin{displaymath}
P(M_{r^*})=\frac{r^*-1}{n}\,\sum^n_{r^*}\,\frac{1}{k-1}\appr...
...c{n}{r^*-1}}\approx\frac{1}{e}\log{e}=\frac{1}{e}
\approx 0.36
\end{displaymath}

以吳學人的三十位閨秀來說,r*大約是11,最好的辦法是「放棄前10位 $\cdots\cdots$」,這樣選中第一名的機會至少會有0.36。換個例子說, 如果你打算從二十歲到四十歲,每年都可考慮結婚。假如你每年只考慮一位對 象,那麼最好的方法大約是M8,也就是說,自你二十八歲起,才開始要 「認真」起來。(年青的時侯多玩玩無妨)。

   

上頁 1234 次頁

回頁首
 
(若有指正、疑問……,可以在此 留言寫信 給我們。)
EpisteMath

EpisteMath (c) 2000 中央研究院數學所、台大數學系
各網頁文章內容之著作權為原著作人所有


編輯:洪瑛 最後修改日期:4/26/2002