2021 TRML 思考賽 第一題組
題目:
從一個 $n\times n$ 的方格紙的左下角,沿著格線依最短路徑走到右上角。
定義 $N(n,k)$ 表示為在行徑過程中轉彎了 $k$ 次的方法數。
例如:
當 $n=2$,$k=1$時,$N(2,1)=2$ 如 (圖1)
當 $n=2$,$k=2$時,$N(2,2)=2$ 如 (圖2)
當 $n=2$,$k=3$時,$N(2,3)=2$ 如 (圖3)
中間可以暴力窮舉的題目這邊不多說明,直接講推一般式的(5)(6)
(5)試求當 $k$ 為偶數時,$N(n,k)$的一般式(以 $n$ 與 $k$ 表示)
注意 這裡的 $k$ 為偶數,在這裡偶數很重要
因為是走最短路徑,所以水平方向的總路徑長與垂直方向的總路徑長皆為 $n$。
而每轉一次彎,行徑方向都會改變一次(以下以 $H$ 表示水平方向、$V$ 表示鉛直方向)
所以會形成 $ H1,V_1,H_2,V_2,…,V{\frac{k}{2}-1},H{\frac{k}{2}},V{\frac{k}{2}},H_{\frac{k}{2}+1} $ 的序列。
其中 $ H_i,1\leq i\leq \frac{k}{2}+1$ 與 $V_j,1\leq j\leq \frac{k}{2} $ 分別代表每個水平線段與鉛直線段的長度。
因此可以列出兩條式子:
令 $H_i’$、$V_j’$ 使得 $H_i=H_i’+1$,$V_j’=V_j+1$,則式子可改寫成如下:
熟悉重複組合(combination with repetition)的人,應該很熟悉這種題目。
可以秒解出水平線段的組合方法有 $C{n-1 \choose \frac{k}{2}}$種,鉛直方向有 $C{n-1 \choose \frac{k}{2}-1}$種。
所以當 $k$ 為偶數時 $N(n,k)=C{n-1 \choose \frac{k}{2}}\times C{n-1 \choose \frac{k}{2}-1}\times 2$。
$\times 2$的原因是因為一開始可選擇水平或鉛直2種情況。
不熟悉重複組合的人去學重複組合,換個方向思考一下。
嘗試看看這道題目:
滿足 $x+y+z+w=6$的非負整數解有幾組?
素養化一下題目敘述:
現有4個編號分別為 $x,y,z,w$ 的桶子以及6顆相同的球,請問將這6顆球放進這4個桶子的方法數有幾種?
考慮有3根相同的隔板,劃分出4個空間,每個空間分別代表一個桶子,而該空間內球的數量就是桶子內球的數量。
所以總方法數就是將3根相同的棍子以及6顆相同的球的排列分法數。
所以答案為 $\frac{(6+3)!}{6!3!}=C{9 \choose 3}=84$。
回到思考賽的題目,因為 $H_i$ 必須要大於 $0$。所以我們將 $H_i$ 變成 $H_i’+1$後,變向成去解了 $H_i’$ 的非負整數解。
對 $V_j$ 同理。
接著就按照上面的想法就好啦。
對於 $H_i$,考慮有 $\frac{k}{2}$個隔板,$n-(\frac{k}{2}+1)$顆球。
所以方法數為 $\frac{(n-(\frac{k}{2}+1)+\frac{k}{2})!}{(n-(\frac{k}{2}+1))!\frac{k}{2}!}=\frac{(n-1)!}{(n-(\frac{k}{2}+1))!\frac{k}{2}!}=C{(n-1) \choose \frac{k}{2}}$
對於 $V_j$,考慮有 $\frac{k}{2}-1$個隔板,$n-\frac{k}{2}$顆球。
所以方法數為 $\frac{(n-\frac{k}{2}+\frac{k}{2}-1)!}{(n-\frac{k}{2})!(\frac{k}{2}-1)!}=\frac{(n-1)!}{(n-\frac{k}{2})!(\frac{k}{2}-1)!}=C{(n-1) \choose \frac{k}{2}-1}$
所以 $N(n,k)=C{n-1 \choose \frac{k}{2}}\times C{n-1 \choose \frac{k}{2}-1}\times 2$。
$\times 2$的原因一樣是因為一開始可選擇水平或鉛直2種情況。
(6)試求當 $k$ 為奇數時,$N(n,k)$的一般式(以 $n$ 與 $k$ 表示)
注意 這裡的 $k$ 為奇數,在這裡奇數很重要
可是偶數比較難
這題就比較簡單了,因為 $k$ 為奇數,所以你的序列會長成這樣:
$H1,V_1,H_2,V_2,…,H{\frac{k-1}{2}},V{\frac{k-1}{2}},H{\frac{k+1}{2}},V_{\frac{k+1}{2}}$
可列出式子:
一樣令 $H_i’$、$V_j’$ 使得 $H_i=H_i’+1$,$V_j’=V_j+1$,改寫式子如下:
所以當 $k$ 為奇數時 $N(n,k)=C{ n-1 \choose \frac{k-1}{2}}^2 \times 2$
$\times 2$一樣是因為一開始可選擇水平或鉛直2種情況。
最後提醒: 當 $k\geq2n$ 時,$N(n,k)=0$喔