在教師甄選的考題常常遇到類似的問題：
◎在箱子內有5顆紅球及3顆藍球，每次取一球，取後不放回。在全數取完的過程中，取出的紅球一直都比藍球多的機率(次數)為何？
◎在選舉開票過程中，1號候選人得票數一直都比2號候選人多的機率(次數)為何？
以上類似的題目都簡而稱為「一路領先」問題。這類題目有個限制，就是只有兩人(球)在競爭，若超過二人的解法就不是這樣算。
一路領先的問題可以轉換成棋盤道路捷徑走法。我們就以110年桃園高中教甄為例：
現在把題目改成：mm個紅球，nn個白球，m≤nm≤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的路徑數量=Cn+1+m−1n+1=Cn+mn+1=Cn+mm−1Cn+1+m−1n+1=Cn+mn+1=Cn+mm−1，A至B的路徑數量=Cm+nm=Cm+nnCm+nm=Cm+nn，因此一路領先的數量=Cm+nm−Cn+mm−1=Cm+nm−Cn+mm−1 =Cm+nn−Cn+mn+1Cm+nn−Cn+mn+1。
回到桃園教甄的題目，違規的路徑數=C4+63=C4+67=120C4+63=C4+67=120，全部路徑數是C104=210C104=210，因此一路領先的數量是210-120=90，結果與手算相同。
也許你已經搞混哪個是m?哪個是n?，總之:違規數量=C大+小大+1=C大+小小−1
沒有留言:
張貼留言