一路領先問題
不記名投票之下,甲得m票,乙得n票,且m\geq n,開票過程中甲的得票數一路領先乙的得票數之情況總共有
1.當領先狀況允許等於時(甲的得票數 \geq 乙的得票數)C^{m+n}_{m}-C^{m+n}_{m+1}
2.當領先狀況不能等於時(甲的得票數 > 乙的得票數)C^{m+n-1}_{m-1}-C^{m+n-1}_{m+1-1}
可將原問題轉換為走捷徑問題,舉例來說明:
問:當甲得5票,乙得3票時,開票過程中甲的得票數大於等於乙的得票數之情況為何?
視為下圖(a),A走到Z的捷徑問題,共有5橫線段3縱線段構成,甲每得一票代表走一小段橫線,乙每得一票代表走一小段縱線,每一個捷徑走法對應到一種得票過程。
如圖(b),則不難發現線段\overline{AV}上的點A、H、O、V為得票數平手的局面,例如O點即為兩橫兩縱,代表過程中甲得兩票乙得兩票的情況,而這在這個例題中是可以被允許的(得票數大於等於)。且更可以發現綠色的點就是違規的情況,故開票的過程中要避免經過綠色的點。
1.當領先狀況允許等於時(甲的得票數 \geq 乙的得票數)C^{m+n}_{m}-C^{m+n}_{m+1}
2.當領先狀況不能等於時(甲的得票數 > 乙的得票數)C^{m+n-1}_{m-1}-C^{m+n-1}_{m+1-1}
可將原問題轉換為走捷徑問題,舉例來說明:
問:當甲得5票,乙得3票時,開票過程中甲的得票數大於等於乙的得票數之情況為何?
視為下圖(a),A走到Z的捷徑問題,共有5橫線段3縱線段構成,甲每得一票代表走一小段橫線,乙每得一票代表走一小段縱線,每一個捷徑走法對應到一種得票過程。
圖(a)
如圖(b),則不難發現線段\overline{AV}上的點A、H、O、V為得票數平手的局面,例如O點即為兩橫兩縱,代表過程中甲得兩票乙得兩票的情況,而這在這個例題中是可以被允許的(得票數大於等於)。且更可以發現綠色的點就是違規的情況,故開票的過程中要避免經過綠色的點。
圖(b)
換句話說,可以先算所有捷徑的走法減去會通過綠色點的走法,即為所求。而要如何算出通過綠色的路徑數量呢?
首先經過綠色的極限情況是發生在線段\overline{GU}上,線段\overline{GU}仿佛形成一道界線,故我們從\overline{GU}畫一條對稱軸,如圖(c),並對A、B、C...等三點做對稱於\overline{GU}的對稱點A_1、B_1、C_1...這邊只取這三個對稱點當代表,則所有A走到Z的捷徑情況都可以被一一對應到從A_1走到Z的情況,但從A_1走到Z的所有情況都會經過\overline{GU}(及違規)。
圖(c)
C^{8}_{5}如圖(d),原始所有路徑(包含違規與不違規)
圖(d)
C^{8}_{6}如圖(e),必通過綠色違規路徑
圖(e)
故所求即為C^{8}_{5}-C^{8}_{6}
所以如果題目改成不能等於,則紅色線段\overline{AV}即變為對稱軸,且並從B點開始走捷徑(因為甲一定要拿到第一票),故同理可知起點變為B,對稱軸變為\overline{AV},故答案為C^{7}_{4}-C^{7}_{5}(全部減1)
留言
張貼留言