201208171457排隊看電影的問題

      筆者在大學時代修習「數理統計」這門課時,曾經遇過一個機率問題,該問題敘述如下:

[問題1]:有200個人排隊要看電影,門票50元,已知其中有100個人身上只帶著剛好是門票錢的50元硬幣,另外100個人只帶著100元鈔票,而收錢賣門票的售票員完全沒有準備任何的零錢,試問:售票員可以順利賣出200張門票的機率為何?

      題目提及「順利賣出200張門票」的關鍵,在於售票員必須能夠順利找錢,比如說他收到錢的順序剛好是50元與100元相間隔:50元, 100元, 50元, 100元, 50元, 100元,..., 50元, 100元,那就能順利賣出200張門票;又比如說收到錢的前三個人順序剛好是:50元, 100元, 100元,那就會發生無法找錢的情形。

      這個問題,我們可以先想比較簡單的情形,若將原題目的200人改成12人,那麼就可以用下面這個示意圖來看,向右一格表示收到50元,向上一格表示收到100元:


注意紅色的路徑就是屬於「無法順利找錢」的路徑,因為在第三個人拿出100元後,售票員就沒錢可找了,而像這樣的路徑特色是「會通過對角線」。

      不論是上圖中的紅色或者藍色路線,我們先算出客人排好隊且於開始買票前,所有可能的排隊情形。使用高中排列組合的知識,有12個人,他們所拿的錢有6個50元與6個100元,這是不盡相異物的排列,任意排好隊準備買票的方法有12!/6!6!=C(12,6)=924種。

      又若假設售票員可以順利賣完票,表示他在收票過程中,收到50元的人數永遠不能落後(大於或等於)收到100元的人數,這樣子的[收錢路徑],應如同圖一中的藍色路線,此類路徑在過程中不會穿過(但可以碰到)對角線。若要算出方法數,由下圖的累計法,可知答案為132種方式:

因此售票員「可以順利賣完門票」的機率為132/924=1/7=0.142857....。

      但原問題中的人數為200人,因此若要像圖二這樣使用累計法,將會非常辛苦,所以要另外想別的辦法喔。這個新的方法如下,請先看下圖:

圖三只是在圖二中最左下方的1的左上方多放一個-1,就可以造成主對角線(1,1,2,5,14,42,132那條線)上方的次對角線上都是0,而這一排0就會使主對角線的數字不會受來自左方與上方(次對角線)的方法數影響。有鑑於此,如果有200個人看電影,我們可以考慮下圖:

圖四

大家所熟知的"巴斯卡三角形"(見註[1])最頂端的1,可以看成是方法數,它會一路往下散播。而上圖告訴我們最左下方紅色的1,會像巴斯卡三角形最頂端的1一樣,一路往右上方散播方法數,到了最右上方的點,方法數為C(200,100)。然後再看下圖:

圖五

同理,最左下方藍色的-1也會一路往右上方散播方法數,到了最右上方的點,方法數為-C(200,99)。把圖四與圖五一起看,就知道200個人看電影時,可以順利找錢的方法數為C(200,100)-C(200,99)種方法。類似的,如果回到圖三,已知有12人,使用新的方法來算,就知道方法數為C(12,6)-C(12,5)=924-792=132,與原來的答案相符。

      其實題目的200人可以改為500人,或者任意的正偶數2n(why正偶數? 因為拿50元的人和100元的人要一樣多),都可以將答案使用組合數C(2n,n)-C(2n,n-1)來表示出方法數喔。設方法數有M種,則M還可以化簡,如下: 

M=C(2n,n)-C(2n,n-1)=C(2n,n)-C(2n,n)*(n/n+1)=C(2n,n)/n+1

所以,所問的機率值剛好就是化M/C(2n,n)=1/n+1。而上面200人看電影的那題,解答就是1/101=0.009900...。

      筆者隨後又想到一個稍微改變條件的問題,若看電影的人數仍為12人,但售票員賣票之前手上恰好有一個50元硬幣,那麼答案若用累計法來計算,可以得出方法數為429種,其計數方式請看下圖: 


至於為何累計時不能超過紫色的線呢? 紫色線的限制,表示付50元的累計人數在過程中最多只能比付100元的人數少一個,而這是因為售票員一開始只有一個50元的緣故。而這時候能不能像上面一樣,填入一個藍色的-1,用新的方法算出上圖中的方法數429呢?大家可以想想看。以上就是筆者的分享。

     

[參考資料]:

[1]Wikipedia--Pascal's Traingle

http://en.wikipedia.org/wiki/Pascal%27s_triangle

(本文作者:連威翔,曾任職於交大理學院科學學士班)

沒有上一則|日誌首頁|沒有下一則
回應
關鍵字
    沒有新回應!





Powered by Xuite