Codeforces #26 D Tickets

題意﹕現在有一個計數器，數值最初為 $k$ ，並有兩個按鈕﹕一是可以讓計數器加一，一是可以讓計數器減一。現在你可以按 $n$ 次加一 $m$ 次減一，若你選取操作的排例的概率是均等，那麼有多少機會使得你在操作中途計數器總是非負？

首先，用圖表的方式去想。假定橫軸是操作的時序，縱軸代表計數器在某個時刻的數值，那麼一個操作順序剛好表示了一副折線圖。像如下的圖代表操作不會引致負數﹕



順道留意﹕終點永遠在座標 $(n+m, n+k-m)$ 。如失敗的話，折線圖必然會與橫線 $y = -1$ 相交，如下圖所示﹕



首先，所有折線圖的數量是 $T = \binom{n+m}{n}$ ，來源可以想像成﹕在 $n + m$ 個時序中任意取 $n$ 個時序進行加一，同樣道理可得出 $\binom{n+m}{m} = \binom{n+m}{n}$ 。如果我們能求所有與 $y = -1$ 相交的折線圖的數量 $S$ ，那麼答案就是 $1 - \frac{S}{T}$ 。說來倒是很容易，但是礙於限制，我們不能直接用公式求算 $S$ 的數量。1978年Cohen利用「反射原理」解決了類同問題，我們也可以試著利用此原理解決問題。

首先留意任何與 $y=-1$ 相交的折線圖，其最後與 $y = -1$ 相交的點，之後必然最終上升至 $(n+m, n+k-m)$ （留意它並非直線上升，中途可能還會下跌，但永遠不會跌至負數值）。這條線從相交點計起長度是 $n+k-m+1$ 。那麼我們試著把這條線「反射」一下，它則一下子掉到 $(n+m, -1-n-k+m-1) = (n+m, m-n-k-2)$ 。例子如下：



藍色點是反射起點，藍色虛線是反射線。留意線過部份反射後的折線圖與原來的圖是一一對應的。另外，新的折線圖擺脫了橫線相交的限制，因為通過反射後折線圖已經肯定是與橫線 $y=-1$ 相交，因此可以看作成在 $(n+m, m-k-n-2)$ 出發，逆時序的加一減一，直至到達 $(0, k)$ 有多少操作，其且每一個圖與原來和橫線相交的圖一一對應。問題是，經這種轉換後我們不清楚被允計使用多少次加一與減一所組成的。設我們被允許 $a$ 次加一 $b$ 次減一，利用反射原理的一一對應關係，我們得到如下式﹕

$$\left\{ \begin{array}{ll} a+b = n+m & \quad \text{(width restriction)}\\ k+a-b = m-n-k-2 & \quad \text{(height restriction)}\\ \end{array} \right.$$

因此我們可得 $a = m - k - 1$ 。而新圖的數量則是 $\binom{n+m}{a} = \binom{n+m}{m-k-1}$ 。又因為每一個新折線圖與原來和橫線相交的圖一一對應，故得 $S = \binom{n+m}{m-k-1}$ 。因此本題的答案是

$$1-\frac{S}{T}=1-\frac{\binom{n+m}{m-k-1}}{\binom{n+m}{n}} = 1-\frac{(m-k)(m-k+1)\cdots m}{(n+1)(n+2)\cdots (n+k+1)}$$


如欲清楚更多反射原理的資料，請參考[1]。

[1] D. I. A. Cohen, Basic Techniques of Combinatorial Theory, John Wiley and Sons, New York (1978).