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

　1│2│3│4　

海外學人相親記（第 2 頁）

李宗元

首頁 | 搜尋

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

‧註釋
‧對外搜尋關鍵字

最佳的選擇

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

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

M_r：放棄前面 k-1 位。自第 r 位起，首次遇到較前均佳者即停。

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

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

P(M_r) 為根據上述辦法，選中第一名的機率
S_k 為根據上述辦法，第 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(A 且 B)。顯然， $P(x_k=1) = \frac{1}{n}$ 。（n 個不同數字亂排，最小的要在第 k 個位置）。至於 P(S_k|x_k=1) 是什麼？假如第一名在第 k 個位置，那麼，按照 M_r，只有下面的情形我們才能選到她：這就是，前面 k-1 個數字（閨秀）中，最小的（最好的）要發生在最前面 r-1 個位置裏。（舉例說，r=3, k=6, 而各位閨秀的名次，依出場次序排，分別為 4,8,5,6,3,1,… 則按照 M₃，我們必須選擇第五位，因為她是臨時第一名，所以真正的第一名就沒有被選到）。顯然，上述事件的機會是 $\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(M₁)=1/n。

我們現在要檢查一下，在上述辦法裏，哪一個r能使P(M_r)最大。把這個r叫做r^*，那麼M_r^*就是最佳的選擇法。看到這裏，比較細心一點的讀者也許會問：你怎麼可以保證沒有再好的辦法呢？換句話說：最好的辦法，一定是在上述這類 $(M_r:r=2,3\cdots)$ 裏面嗎？答案是肯定的，證明也不是很難；但是又要再費一番口舌，我想就算了罷。讀者如要深究，可參照資料[4]，[5]，好好想一想。 ⁴ 我現在將 P(M_r) 簡寫作 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

由這裏你可以注意到， $\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)式中計算出來。

這裏有趣的是，雖然 r^* 隨 n 而變，但當 n 很大時， $\frac{r^*}{n}$ 幾乎沒有什麼變化。（事實上，實際的數據顯示，n=20 已經可算「很大」了）。怎樣看出這點來？這裏我們要提到「自然對數」 $\log$ 。這是以 $e\approx2.718$ 為底的對數函數。（有人將這 $\log$ 寫作 $\log_e$ 或者 $\ln$ ）。它是怎樣來的？最好的定義方法是： $\log{t}$ 是曲線 $y=\frac{1}{x}$ 與 x 軸在 x=1 和 x=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。換個例子說，如果你打算從二十歲到四十歲，每年都可考慮結婚。假如你每年只考慮一位對象，那麼最好的方法大約是M₈，也就是說，自你二十八歲起，才開始要「認真」起來。(年青的時侯多玩玩無妨)。

　1│2│3│4　


	（若有指正、疑問……，可以在此留言或寫信給我們。）

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

編輯：洪瑛

最後修改日期：4/26/2002