網頁

2021年11月12日 星期五

一路領先的數學問題

 在教師甄選的考題常常遇到類似的問題:

◎在箱子內有5顆紅球及3顆藍球,每次取一球,取後不放回。在全數取完的過程中,取出的紅球一直都比藍球多的機率(次數)為何?

◎在選舉開票過程中,1號候選人得票數一直都比2號候選人多的機率(次數)為何?

以上類似的題目都簡而稱為「一路領先」問題。這類題目有個限制,就是只有兩人(球)在競爭,若超過二人的解法就不是這樣算。

一路領先的問題可以轉換成棋盤道路捷徑走法。我們就以110年桃園高中教甄為例:

解答
取一白球相當於向右走一格,取一紅球相當於向上走一格,因此從A走到B相當於6白4紅(或6個右4個上)的排列數,即\(C^{10}_4=210\)種走法。但題意要求過程中白球數需大於等於紅球數,相當於行走在著色區域(對角線的右半部),見上圖;由於本題數字小,直接從A開始手算至B點,共有90種走法符合要求,因此機率為\({90\over 210}=\bbox[red,2pt]{3\over 7}\)。

現在把題目改成:\(m\)個紅球,\(n\)個白球,\(m\le n\),答案應該是什麼?

大部份一路領先的題目,把過程中「平手」也算進去,也就是只要白球數大於或等於紅球數,都算是一路領先。因此我們把起點A定位在原點,即A(0,0),則終點在B(n,m),將對角線平移往上移一格(直線方程式為y=x+1),簡稱為紅線。所有從A到B的路徑,只要碰到紅線就不符合一路領先的條件。若我們能求出所有違規的路徑,就能求出合乎一路領先的路徑數量。

任何一條違規路徑一定會碰到紅線,假設此路徑經過點P(P在紅線上),則A至P的路徑數量與A'至P的路徑數量是相同的(A'與A對稱於紅線)。因此從A至B的違規路徑數量與A'至B的路徑數量是相同的,而且從A'出發到B的路徑都是違規的。A'至B的路徑數量=\(C^{n+1+m-1}_{n+1} =C^{n+m}_{n+1}=C^{n+m}_{m-1}\),A至B的路徑數量=\(C^{m+n}_m=C^{m+n}_n\),因此一路領先的數量\(=C^{m+n}_m-C^{n+m}_{m-1}\) =\(C^{m+n}_n-C^{n+m}_{n+1}\)

回到桃園教甄的題目,違規的路徑數=\(C^{4+6}_3=C^{4+6}_7=120\),全部路徑數是\(C^{10}_4=210\),因此一路領先的數量是210-120=90,結果與手算相同。

也許你已經搞混哪個是m?哪個是n?,總之:違規數量=\(C^{大+小}_{大+1}=C^{大+小}_{小-1}\)

沒有留言:

張貼留言