上頁 123 次頁

摘麥穗問題 (第 2 頁)

楊照崑

 

首頁 | 搜尋

.原載於科學月刊第三卷第五期
.作者當時任教於中央數學系

註釋
對外搜尋關鍵字
 
問題的開始

我們首先看看摘麥穗的故事。故事的梗概是這樣的;一個小女孩同她舅舅在麥田畔散步,這舅舅對小女孩說: 「現在我希望妳在走完這片麥田時,摘那枝最大的麥穗給我。妳只許摘一次,而且不許回頭去摘。」 這小女孩走著看著。始終覺得前面有更大的麥穗,一直捨不得用去這唯一的機會。快走完麥田的時候, 她才發現大麥穗都已過去了,前面都是些小的,後悔不已。故事的最後是這位舅舅的一套人生哲學的教訓。

我們的問題是,這個小女孩應當怎樣去摘,才最可能摘到那串最大的麥穗?與此問題類似的問題很多,我們舉幾個例子。

(一) 某公司招考工作人員,每天考一個人,現有五十人報考。考完的當天老闆就得決定用不用這個人, 如果不用他,他即拂袖而去,此去不回。問題是:如何取得那最好的申請者。

(二) 某城有二十間房子出租,某甲希望租到那間最理想的房子,但在看房子之前,他無法知道房子的好壞。 假定他看了房子,他就立刻得決定租不祖,不租就被別人祖去了。問題是:他將如何去看房子,以期租到最理想的房子?

(三) 老師分二十個蘋果給二十個小朋友。蘋果在袋子裡看不見大小。現在你站在最前面, 老師每拿出一個蘋果之後都先問你要不要,如果妳不要,她就把蘋果拾別人。 假定你只能要一次,你如何最可能的要到那個最大的蘋果?

   
 
問題之一

為了簡化許多不必要的名詞,以上的問題可以想成一個袋子裡有N個球。每個球上有它半徑的數目。假定半徑都不相同, 大小我們不知道。我們每次隨便取一個球出來,看了半徑之後就得決定要不要。如果要,取球就此停止。如果不要, 再往下取,但不准再回頭要原先的球。這樣下去,直到N個球取完為止。我們的目的是取到那個最大半徑的球。 1

在此我們定球的等級為;最大球為N等,次大球為N-1等,$\cdots \cdots$,最小的球為1等。

當我們取出第一球時,我們看見它的半徑是r1,但不知它的等級。現在有二個選擇。一是我們就要了它, 二是我們不要它,取下一個看看。如果我們要了它,我們拿到最大球的機會顯然是$\frac{1}{N}$

如果我們不要它,我們看到了第二個球的半徑是r2。我們又有二個選擇,要不要它?如果我們就要這第二個球, 我們拿到最大球的機會仍是$\frac{1}{N}$。但仔細一想,如果第二個球的半徑比第一球小,我們要它也沒有用, 因它顯然不是最大的,我們不如往下拿。因此當我們拿到第二球時。我們的選擇是:

1. 如果r2<r1,我們往下拿。

2. 如果r2>r1,我們取第二球,或

3. 如果r2>ri,我們仍然往下拿,那就是說我們在任何情形下,不拿前面兩個球。

同理,當我們看到第三球的半徑r3時,我們的選擇是:

1. 如果 $r_3<\max(r_1,r_2)$r3已顯然非最大,我們往下取。式中$\max(r_1,r_2)$表示二數中較大者。

2. 如果 $r_3>\max(r_1,r_2)$,我們取第三球,或

3. 如果 $r_3>\max(r_1,r_2)$,我們仍然往下拿,那就是說,在任何情形下,我們不拿前面三個球。

如此,我們的一般規則是:

1. 在任何情形下,不拿前面s-1個球。

2. 從 s 球開始,凡拿到一個球大於 $\max(r_1,r_2,\cdots \cdots,r_{s-1})$ 的,即取之。如果一直拿不到, 那表示最大球在前s-1球之中,只好承認失敗。

現在我們以四球為例,看看情形如何。我們以 1,2,3,4 表示球的等級,(表一)表示它們的出場序。 根據排列的算法,共有 $4\!=24$ 種出場的情形,根據隨便取的假定,每種出場序有同樣發生的可能性 $\frac{1}{24}$

按照上述的規則,若s=1,就是我們就要第一個,我們有6種排列法可以拿到最大的(即第四列的全部), 因此我們拿到最大球的或然率是$\frac{6}{24}$。若s=2,則凡打「$\ast$」號的出場序,我們都可拿到最大的球, 其或然率為$\frac{11}{24}$。若s=4,則凡打「$\circ$」號的出場序,我們都可以拿到最大球,其或然率為$\frac{10}{24}$。 若s=4,則只有以4結尾的排列才可以使我們拿到最大的球,其或然率為$\frac{6}{24}$

由此可見拿到最大球最好的方法是令s=2,也就是說越過第一球,從第二球開始選大於第一球的那個球。

對一般N而言,我們若從第s球開始比較,我們拿到最大球的或然率是 2

\begin{displaymath}
P_N(s) = \frac{s-1}{N}(\frac{1}{s-1}+\frac{1}{s}+\frac{1}{s+1}+\cdots
+ \frac{1}{N-1})
\end{displaymath}


\begin{displaymath}
\begin{array}{rcrcrcrc}
& 1\, 2\, 3\, 4&& 2\, 1\, 3\, 4& \c...
...\, 3\, 1& \ast & 3\, 4\, 2\, 1 && 4\, 3\, 2\, 1 \\
\end{array}\end{displaymath}

表一:四球的出場序



N s* PN(s*) N s* PN(s*)
1 1 1.00 15 6 0.39
2 1,2 0.50 20 8 0.38
3 2 0.50 30 12 0.38
4 2 0.46 40 16 0.38
5 3 0.43 50 19 0.37
6 3 0.43 60 23 0.37
7 3 0.41 70 27 0.37
8 4 0.41 100 38 0.37
9 4 0.41 1000 369 0.37
10 4 0.40 極大 $\frac{N}{e}$ e-1

表二:最佳猜球法,只猜一次.N表示球數,s*表示開始可要的球,PN(s*)表示猜對的或然率.

從上式中,我們不難代入所有的 $s=1,2,\cdots ,N$ 找出能使 PN(s) 最大的 s,我們用 s* 表示。表二中有許多 s* 的值。

從表二中顯示出,當球數愈多時,即使我們用最好的方法,找到最大球的機會仍會減小。這並不難想見, 因為球多了,那唯一最大的就難找了。根據理論上的推算 3 ,這或然率並不趨近於零, 而趨近於e-1。這裹的e是自然對數的底,約等於2.72。因此我們看到,此種猜法猜對的或然率永遠大於$\frac{1}{3}$。 當球數很多的時候,這是一件不容易想到的事實。同時我們也可以推演出當N很大時, 最佳值s*略等於N e-1(同上註)。我們不用看表二,只要把球數N除以2.72,即可大約找到我們開始要選球的位置了。

   
 
問題之二

在摘麥穗問題中,如果我們把條件放寬一點,允許小女孩先摘一枝,然後可以再換一次,選擇的方法又如何呢? 我們不難想像這種騎馬找馬的辦法在日常生活中是很常見的。不過換的次數不能太多,否則一直找大的換下去, 一定可以換到最大的那個。我們假定只能換一次。

仍然回到拿球的問題上來。現在我們允許猜球者換一次。首先我們也許會想到先取第一個,然後等一段時間,再看大的換。 根據問題之一同樣的推理,我們可以看出先取第一個的方法並不見得最好,因為第一值是最大球的或然率只有$\frac{1}{N}$。 我們先等一下才取第一個球。第一個球取出之後,我們再等一下,看到更大的球就換。第一球取出之後要等多久才換, 因N而異。我們定R(r,s)為下列的取球法:

1. 先越過t-1個球,在任何情形下都不取。

2. 從t球開始,凡有比 $\max(r_1,r_2,\cdots\cdots,r_{t-1})$大的,取之。

3. 從s球開始,凡有比 $\max(r_1,r_2,\cdots\cdots,r_{t-1})$大的球,換之。如果在rs-1之間未取球,則在s之後,仍可換一次。

R(t,s)中,若s=t+1,則表示取過第一球之後,立刻就可以換。這個問題在計算上比問題之一複雜很多, 我們不把公式列出來。表三中顯示出最好的ts使我們容易拿到那個最大的球。

N tX s* P N t* s* P
1 1 1 1.00 15 4 6 0.63
2 1 2 1.00 20 5 8 0.62
3 1 2 0.83 30 7 12 0.62
4 1 2 0.71 40 10 16 0.60
5 2 3 0.71 50 12 19 0.60
6 2 3 0.69 60 14 23 0.60
7 2 3 0.67 70 16 27 0.60
8 2 4 0.66 100 23 38 0.60
9 3 4 0.65        
10 3 4 0.65 極大 $\frac{N}{e^\frac{3}{2}}$ $\frac{N}{e}$ 0.59

表三:可換一球之最佳取法。N表示球數,t*s*即第一次與第二次超過之球數,P為猜對的或然率。

從表三我們可以看出,我們拿到最大球的或然率始終大於$\frac{1}{2}$。所以如果依照上法拿球換球, 我們找到最大球的機會比找不到的機會還大。

仔細看表三中的s*,我們會發現它與表二中的s*相同。我們看出現在的方法只是不使在開始時越過的球太多。

   
 
問題之三

在前面二個問題中,目標都在最大的麥穗上。如果最大的麥穗在前面我們越過的地方,我們就什麼都不要了。 這種「寧為玉碎」的辦法,有時並不可取。在例 (一)、(二)、(三)中,公司總得找一個人,我們總要住房子, 孩子總要吃蘋果,最好的幸運不是人人都有,我們如何退而求其次盡可能選出最好的人選,房子,與蘋果呢?

再用袋子裡拿球的例子來說,假定我們拿到最小的球可得1分,次小的球可得2分,…,最大的球得N分, 我們只能選一次,不准回頭選,但必須選一個,我們如何選才可以得到高分呢?

顯然的.如果我們隨便取一個球,或就取第一個球,我們得分的期望值是

\begin{displaymath}
\frac{(1+2+3+\cdots \cdots+N)}{N}=\frac{N+1}{2}
\end{displaymath}

如果有一百個球,隨便取的話,得分的期望值是50.5,但如果根據理論推出最好的取法,我們可以使得分的期望值高達97.4。 解決這個問題的公式與演算相當的複雜,但我們並不難推出解決此問題的方向。

我們既要越過第一球,同理我們也可以越過前面若干個球。假定球數N=10,假定我們越過前三球。如果第四球的分數比前三球都高, 我們自然取它(否則我們就定為越過前四球了)。如果它分數低,我們拿第五球,等等,如果我們拿到第八球,還未遇到分數高的球, 我們就得小心了,因為所剩的機會已經不多,第八球的分數即使不很高,如果「像樣」的話, 我們就可以要了。例如第八球是已拿球中分數位第二位的,我們就該取下了。如果第八球實在很小, 我們不妨再試第九球,但條件更得降低了。如果第九球在前面九個球中位於第六位以上就值得要了, 因為最後一球的期望值(屆時你非要不可)只有5.5。

因此,問題的取法是

1. 先越過若干球,一定不取。
2. 此後每取一球,看它在前面已取出球中所佔的等級與它後面尚有多少球作一取捨。

對一般N而言,表格過於繁瑣,我們只舉N=4為例,看最佳的取法如何。N=4時最佳取法是:

1. 越過第一球.一定不取。
2. 若第二球比第一球大,取之,否則取第三球。
3. 若第三球在前面三球 (一、二、三,三球)中位第二位以上,取之。否則取第四球。

如此取法的得分期望值為 3.125,比隨便取的2.5大了不少。對一般大 N 而言,最初越過的球數約等於 $\frac{N}{3}$ 與問題之一的 $\frac{N}{e}$ 差不太多。由公式演算出的最佳取法,得分的期望值始終大於 N-3, 也就是說我們平均可取得第四大的球,當球很多的時候這是一個不容易直覺到的事情。

   
 
問題之四

摘麥穗問題還可以用到交男女朋友上去。實際上.這個問題在許多數學或統計雜誌上就是以「選美問題」或「婚姻問題」發表的。 我們借用童話堛漸桹角子與森林公主來討論此問題的另一發展。

森林公主住在巫婆家裹,巫婆有三個女兒。有一天王子到巫婆家門前來帶公主走。他不認得誰是公主誰是巫婆的女兒; 但他知道公主是最漂亮的。(巫婆女兒也不太醜,否則就太容易猜了。)猜的方式與問題一樣,女孩子一個個出來, 前門出來後門進去,王子得立刻下決心帶不帶她走,不准回頭帶。王子的目的是認出公主。到目前為止與問題之一完全一樣。 現在另加的條件是,巫婆有權安排公主出場的次序,她不希望王子認出公主。

假定王子足智多謀,而巫婆卻也鬼計多端,二個都是絕頂聰明的人。現在看:照問題之一的解法, 王子最好的選擇法就是越過第一位出場的女孩子,從第二位開始比較,帶比第一位漂亮的回家。 但巫婆她也知道問題之一的辦法,她把公主放在第一位,王子不就失敗了嗎?但王子的智力不弱.他也會想到這點, 猜第一位不就準成功了嗎?但巫婆亦非無能之輩,她把公主換到第二位就是了…。如此勾心鬥角,到了認人的時刻, 王子當怎樣認,巫婆當怎樣排,才可以造成自己最有利的戰略呢?

首先很明顯的一點是雙方好的戰略都不是固定的而是或然的。換言之,若巫婆最好的方法是把公主放在第幾位出場, 王子亦可同樣推出這個位置,結果一猜即中,可見巫婆無固定排法。另方面,如果王子最好的方法是 1.帶走第一位,或惟一其他的選擇 2.不帶第一位,巫婆都可以使他失敗。因此他的猜法也不是固定的。 或然的戰略是這樣的:巫婆以或然率 p1 把公主排在第一位,p2,p3,p4,把公主放在第二、三、四的位置。 到時候臨時抽籤或丟骰子(以上述的或然率)安排公主的位置。王子可以算出巫婆的分配法 p1, p2, p3, p4, 但卻無法確定籤或骰子的決定。如果我們用 si 表示王子越過前面 i 個女孩子的猜法,則王子好的戰略也是以 p1, p2, p3, p4(不一定與巫婆的相同)的或然率採取sO, s1, s2s3 的方法。

我們以x表示王子的戰略,y表示巫婆的戰略,p(x,y)表示在此兩戰略下,王子猜出公主的或然率。 王子希望p(x,y)愈大愈好,而巫婆希望p(x,y)愈小愈好。因王子與巫婆都極聰明, 假定他們都找到了他們的最佳戰略x*y*。那麼x*y*該有下面的性質4

1. 如果王子不用最佳戰略x*,而巫婆用她的最佳戰略y*.那麼王子成功的機會必然比他用最佳戰略時小,也就是說.對任何王子的數略 x$p(x,y^*)\leq p(x^*,y^*)$。 item2. 同理,如果巫婆不用她最佳戰略 y*,而王子用他最佳戰略 x*,那麼王子成功的機會會比巫婆用 y* 時大, 也就是,對任何巫婆的戰略 y$(x^*,y)\geq p(x^*,y^*)$

如果兩個都不用最佳戰略說?那麼兩個笨蛋在一起,什麼怪事都可能發生,我們不必為他們傷腦筋。

如何求出滿足1式與2式的x*y*是遊戲論 (Game Theory) 中的基本問顧,往往要用電子計算機硬找。但問題本身的答案並不複雜。

假定巫婆可以隨意安排這四個女孩的位置。巫婆最佳的方法是同以1/4的或然率安排下面任何一種出場序:

\begin{displaymath}
1234,\quad 2341,\quad 3412,\quad 4123,
\end{displaymath}

式中1,2,3,4分別表示女孩子漂亮的程度,4代表公主。王子最佳的猜法是隨便猜.他成功的或然率是0.25 5

假定巫婆只可以安排公主的次序,三個女兒不受指揮爭先恐後的亂排,那麼巫婆最佳戰略y*是: 以6/17,3/17,2/17,6/17的或然率把公主排在第一、二、三、四位置上。

而王子的最佳戰略x*是:以 6/17,6/17,3/17,2/17 的或然率用 s0, s1, s2s3 的猜法。 (si 在前面定義過,即先越過 i 個女孩的方法。)

在這種情形下,王子猜對的或然率是 0.353,比 0.25(王子不用心計隨便猜)大,但比 0.458(巫婆不用心計隨便排)小。 雙方用計,皆有所獲,巫婆以較大的或然率把公主放在頭尾,很合乎我們的直覺。

對一般 N 而言,如果某人可以安排全部的出場序,他可以使猜者猜對的或然率減至 1/N。 但如果他只有權安排最好的(或最好的只有權決定自己隱藏的位置),那麼當雙方都用最佳戰略時, 猜者猜對的或然率約為 $\frac{1}{\log N+1.6}$。由此可見,若有人(聰明人)在出場次序上用計, 當 N 很大的時候幾乎無法猜到最好的。

   

上頁 123 次頁

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

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


編輯:鄧惠文 最後修改日期:4/29/2002