上頁　1│2│3　次頁

摘麥穗問題 （第 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})$大的球，換之。如果在r與s-1之間未取球，則在s之後，仍可換一次。

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

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, s2 與 s3 的方法。

我們以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, s2 與 s3 的猜法。 (si 在前面定義過，即先越過 i 個女孩的方法。)

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

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

   

上頁　1│2│3　次頁

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

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


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