TRML思考賽-1

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} $ 分別代表每個水平線段與鉛直線段的長度。
因此可以列出兩條式子:

$$\begin{cases} H_1+H_2+H_3+...+H_{\frac{k}{2}}+H_{\frac{k}{2}+1}=n\\ V_1+V_2+V_3+...+V_{\frac{k}{2}-1}+V_{\frac{k}{2}}=n \end{cases}$$

令 $H_i’$、$V_j’$ 使得 $H_i=H_i’+1$，$V_j’=V_j+1$，則式子可改寫成如下:

$$\begin{cases} H_1'+H_2'+H_3'+...+H_{\frac{k}{2}}'+H_{\frac{k}{2}+1}'=n-(\frac{k}{2}+1)\\ V_1'+V_2'+V_3'+...+V_{\frac{k}{2}-1}'+V_{\frac{k}{2}}'=n-\frac{k}{2} \end{cases}$$

熟悉重複組合(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}}$

可列出式子:

$$\begin{cases} H_1+H_2+H_3+...+H_{\frac{k-1}{2}}+H_{\frac{k+1}{2}}=n\\ V_1+V_2+V_3+...+V_{\frac{k-1}{2}}+V_{\frac{k+1}{2}}=n \end{cases}$$

一樣令 $H_i’$、$V_j’$ 使得 $H_i=H_i’+1$，$V_j’=V_j+1$，改寫式子如下:

$$\begin{cases} H_1'+H_2'+H_3'+...+H_{\frac{k-1}{2}}'+H_{\frac{k+1}{2}}'=n-\frac{k+1}{2}\\ V_1'+V_2'+V_3'+...+V_{\frac{k-1}{2}}'+V_{\frac{k+1}{2}}'=n-\frac{k+1}{2} \end{cases}$$

所以當 $k$ 為奇數時 $N(n,k)=C{ n-1 \choose \frac{k-1}{2}}^2 \times 2$
$\times 2$一樣是因為一開始可選擇水平或鉛直2種情況。

最後提醒: 當 $k\geq2n$ 時，$N(n,k)=0$喔