上頁 1234 次頁

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

李宗元

 

首頁 | 搜尋

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

註釋
對外搜尋關鍵字
 
退而求其次

這個標題可能會引起誤會。我的意思是,如果你把眼光稍為放低一點, 能夠選中第一名或第二名就好的話,那麼你應該採取怎樣的手段?

很自然地,一開始你仍應按以前的辦法進行,自第r位起,等候第一 個臨時第一名。但是如果等了一段時間,佳人尚未出現,你心堳K難免緊 張起來:是不是第一名已成漏網之魚? (已經在最前面r-1位中出現了)。所以你應該自第s位(s>r)起,首次碰到臨時第一名或臨時 第二名時,你都一把抓住,因為臨時第二名也可能會是實際第二名。我們也 可以證明,最好的手段,就在這一類堙A不過我也不證明了。我再簡寫如下:

Mr,s:自第r位起,選擇臨時第一。自第s位起,(如果以前尚未選定), 選擇臨時第一或臨時第二

我們現在來算Mr,s的成功機率。符號如前。

\begin{displaymath}
\begin{eqalign}
P(M_{r,s})=&\sum^n_{k=r}\,P(S_{k},x_k=1 \mbo...
...} 2)\\
=&\sum^n_{k=r}{P(S_k,x_k=1)+P(S_k,x_k=2)}
\end{eqalign}\end{displaymath} (6)

(i) $r\leq k<s$: $P(S_k\vert x_k=1)=\frac{(r-l)}{(k-1)}, P(S_k,x_k=1)=\frac{(r-1)}{n(k-1)}$
(ii) $r\leq k<s$: $P(S_k,x_k=2)=P(S_k,x_k=2 \mbox{{\fontfamily{cwM0}\fontseries{m}\selectfont \cha...
...0pt plus0.2pt minus0.1pt{\fontfamily{cwM1}\fontseries{m}\selectfont \char 40}})$

(因為如果第k位是第二名,而第一名出現在先,則按照上述辦法, 第k位根本不會被選到)。

現在

\begin{displaymath}
\begin{eqalign}
P(x_k=2\mbox{\hskip 1.2pt plus0.4pt minus0.2...
...{m}\selectfont \char 40}}) &= \frac{(r-1)}{(k-1)}
\end{eqalign}\end{displaymath}


\begin{eqnarray*}
P(S_k,x_k=2)&=&\frac{r-1}{k-1}\cdot\frac{(n-1)-(k-1)}{n(n-1)}\\
&=&\frac{r-1}{n(k-1)}-\frac{r-1}{n(n-1)}
\end{eqnarray*}


(iii)$s\leq k$: $P(S_k\vert x_k=1)=\frac{r-1}{k-1}\cdot\frac{s-2}{k-2}$, 因為這時第k位要被選中,一定是a:前k-1位中最好的要在前r-1位堙A 而且b:前k-1位中次好的要在前s-1位中。注意 $\frac{(s-2)}{(k-2)}$P(b|a) 。所以

\begin{displaymath}
P(S_k,x_k=1)=\frac{1}{n}\cdot\frac{r-1}{k-1}\cdot\frac{s-2}{k-2}
\end{displaymath}

(iv)$s\leq k$:與(iii)中理由一樣,我們得到

\begin{displaymath}
P(S_k,x_k=2)=\frac{1}{n}\cdot\frac{r-1}{k-1}\cdot\frac{s-2}{k-2}
\end{displaymath}

把所有上面結果放進(6)式堙A我們就有

\begin{displaymath}
\begin{eqalign}
P(M_{r,s})=&\sum^n_{k=r}\,P(S_k,x_k=1\mbox{{...
...& +\frac{2(r-1)}{n}-\frac{2(r-1)(s-2)}{n(n-1)}\\
\end{eqalign}\end{displaymath} (7)

我們再討論,當 n 很大時,最好的 rs=r*,s*)以及 P(Mr*,s*) 該是多少。因為(7)式較複雜,最快的方法,就是將這個非連續變數的式子,用連續變數的式子來取代,(discrete $\rightarrow$ continous,這是一般應用數學中的慣技), 然後再用微分的方法。這塈琤u得向一般中學同學們作個道歉,這也是不得已的事。前一節堛熊痕G,你如用微分的方法,也可更快得到,至少可以省去了整頁的篇幅。

我們令

\begin{displaymath}
x=\frac{r}{n},\qquad y=\frac{s}{n}
\end{displaymath}

根據前面的經驗,當n很大時,r*s*也應該很大。因此如果 (r,s)(r*,s*)附近的話,rs也都很大,所以

\begin{displaymath}
\sum^{s-1}_{k=r}\,\frac{1}{k-1}\approx\log{\frac{s}{r}}=\log{\frac{y}{x}}
\end{displaymath}

你若稍為觀察,可見(7)式右方與下式相近
\begin{displaymath}
f(x,y)=2x\log{\frac{y}{x}}-x(y-x)+2x-2xy
\end{displaymath} (8)

現在我就當x,y為連續變數,求f(x,y)的最大點(x*,y*)。根據微分的方法,(x*,y*)應是下面兩式的解:

\begin{displaymath}
\frac{\partial f}{\partial x}=0,\quad \frac{\partial f}{\partial y}=0
\end{displaymath}

計算這兩個偏微分,分別得到

\begin{displaymath}
-2x+3y=2\log{\frac{y}{x}},\quad \frac{2x}{y}=3x
\end{displaymath}

由此我們得到 $y^*=\frac{2}{3}$以及
\begin{displaymath}
-\log x=1+\log (\frac{3}{2})-x \approx 1.405 -x
\end{displaymath} (9)

這是個「超越方程式」,x*是(9)式在(0,1)間的解。x*的近似值並不難求,見圖5。你如有個小型計算機,不消花多少時間,



圖5

就可以找出 $x^*\approx 0.347$。再從(8)和(9),你就得到

\begin{displaymath}
f(x^*,y^*)=x^*(2-x^*)\approx 0.574
\end{displaymath}

所以我們新相親法的答案是

\begin{displaymath}
r^*\approx 0.347n,s^*\approx \frac{2}{3} n ,P(M_{r^*,s^*})\approx 0.574
\end{displaymath}

你有超過一半以上的機會,可以選中第一名或第二名!這和隨意亂選一位的成 功機會$(\frac{2}{n})$,真是天淵之別。你還堅持數學無用嗎?

   

上頁 1234 次頁

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

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


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