# 2024TRML思考賽
2024TRML思考賽的題目是十題的題組，其中剛好是十題的組合題，利用排列組合技巧與機率解就可以解決所有題目，所以將題目整理後放在這並附上思路與解析。
## 題目敘述
設$S$是由某些正整數所組成的集合。我們以$c(S)$表示集合$S$所含**相鄰數對**$(i,i+1)$的組數。
例如：$S=\{1,2,3,4,6,7,9\}$中的相鄰數對共有以下4組：
$$\{1,2\},\{2,3\},\{3,4\},\{6,7\}$$
此時，$c(S)=4$。
\
設$X=\{1,2,3,...,n\}$,其中$n$為正整數。對非負整數$k≤n$，我們令 $f_n(k)$表示在$X$的子集合中，滿足$c(S)=k$的所有子集合$S$之個數。
例如:集合$X_4$中滿足$c(S)=1$的子集合$S$都恰有1組相鄰數對，此種子集合$S$共有以下5種：
$$\{1,2\},\{2,3\},\{3,4\},\{1,2,4\},\{1,3,4\}$$
故$f_4(1)=5$：而滿足$c(S)=2$的子集合$S$都恰有2組相鄰數對，此種子集合$S$共有2種：
$$\{1,2,3\},\{2,3,4\}$$
故$f_4(2)=2$。
\
本題組有兩個主要的評量目標：其一是求出$X_n$中有多少種的子集合$S$滿足相鄰數對的組數$c(S)=k$，即求$f_n(k)$的值；另一則是計算$X_n$中所有子集合或至少(恰)有$k$個元素的所有子集合$S$之$c(S)$值的總和。
例如：$X_n$中恰含2個元素的子集合$S$共有6種：
$$\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\},\{3,4\}$$
其$c(S)$值分別為1,0,0,1,0,1，此時，這些$c(S)$值的總和為$1+0+0+1+0+1=3$。
又如$X_4$中滿足$c(S)>0$的子集合$S$共有以下8種：
$$\{1,2\},\{2,3\},\{3,4\},\{1,2,4\},\{1,3,4\},\{1,2,3\},\{2,3,4\},\{1,2,3,4\}$$
其$c(S)$值分別為1,1,1,1,1,2,2,3，因此，$X_4$的所有子集合$S$之$c(S)$值的總和為$1+1+1+1+1+2+2+3=12$。
---
### Problem 1
試求集合$S=\{1,3,4,5,6,8,9,10,12,13\}$的$c(S)$值，並列出$S$的所有相鄰數對。
:::spoiler :relieved: Hint:純列舉
相鄰的數對共有$\{3,4\}、\{4,5\}、\{5,6\}、\{8,9\}、\{9,10\}、\{12,13\}$，共6組相鄰數對
故$c(S)=6$
:::
### Problem 2
試求$f_5(1)$的值，請說明理由或列出$X_5$的子集合中滿足$c(S)=1$的所有子集合$S$。
:::spoiler :relieved: Hint:技巧性列舉/純列舉
利用插空法，先假設沒有被選取到的數字為`X`，取的數字假設為`O`，因為只能有一組相鄰數對，則分成以下兩種case討論：
(1)在3個`X`中插入`OO`一對相鄰數對
假設排列情況為`XXOOX`，則這個子集合為$\{3,4\}$
3個`X`共有4個位置可以插入，故有$P_{1}^{4}$種情況
(2)在2個`X`中插入`OO`一對相鄰數對和`O`一個數字
假設排列情況為`OOXXO`，則這個子集合為$\{1,2,5\}$
2個`X`共有3個位置可以插入，又`OO`相鄰數對與`O`可以交換，故有$P_{2}^{3}$種情況
綜合以上兩種case，可以得出$f_5(1)=P_{1}^{4}+P_{2}^{3}=10$
---
<另解>純列舉
$X_5$的子集合中滿足$c(S)=1$的所有子集合$S$有$\{1,2\}、\{1,2,4\}、\{1,2,5\}、\{2,3\}、\{2,3,5\}、$
$\{3,4\}、\{1,3,4\}、\{4,5\}、\{1,4,5\}、\{2,4,5\}$，共10個
故$f_5(1)=10$
:::
### Problem 3
試求$f_6(2)$的值，請說明理由或列出$X_6$的子集合中滿足$c(S)=2$的所有子集合$S$。
:::spoiler :relieved: Hint:技巧性列舉/純列舉
方法同Problem 2。
利用插空法，先假設沒有被選取到的數字為`X`，取的數字假設為`O`，可能包含兩組兩個相鄰數對，或是一組三個相鄰數對，則分成以下三種case討論：
(1)在3個`X`中插入`OOO`一組三個相鄰數對
3個`X`共有4個位置可以插入，故有$P_{1}^{4}$種情況
(2)在2個`X`中插入`OOO`一組三個相鄰數對和一個數字`O`
2個`X`共有3個位置可以插入，且插入的`OOO`和`O`可以交換，故有$P_{2}^{3}$種情況
(3)在2個`X`中插入`OO`兩組兩個相鄰數對
2個`X`共有3個位置可以插入，但兩個`OO`為同物，故有$C_{2}^{3}$種情況
綜合以上三種case，可以得出$f_6(2)=P_{1}^{4}+P_{2}^{3}+C_{2}^{3}=13$
---
<另解>純列舉
$X_6$的子集合中滿足$c(S)=2$的所有子集合$S$有$\{1,2,3\}、\{1,2,3,5\}、\{1,2,3,6\}、$
$\{2,3,4\}、\{2,3,4,6\}、\{3,4,5\}、\{1,3,4,5\}、$
$\{4,5,6\}、\{1,4,5,6\}、\{2,4,5,6\}、$
$\{1,2,4,5\}、\{1,2,5,6\}、\{2,3,5,6\}$，共13個
故$f_6(2)=13$
:::
### Problem 4
試求$f_7(3)$的值，請說明理由或列出$X_7$的子集合中滿足$c(S)=3$的所有子集合S。
:::spoiler :relieved: Hint:技巧性列舉
方法同Problem 3。
利用插空法，先假設沒有被選取到的數字為`X`，取的數字假設為`O`，因為一定要有三組相鄰數字，分析可能包含的數對，並分成以下三種case討論：
(1)在3個`X`中插入`OOOO`一組四個相鄰數對
3個`X`共有4個位置可以插入，故有$P_{1}^{4}$種情況
(2)在2個`X`中插入`OOOO`一組四個相鄰數對和一個數字`O`
2個`X`共有3個位置可以插入，且插入的`OOOO`和`O`可以交換，故有$P_{2}^{3}$種情況
(3)在2個`X`中插入`OOO`一組三個相鄰數對和`OO`一組兩個相鄰數對
2個`X`共有3個位置可以插入，且插入的`OOO`和`OO`可以交換，故有$P_{2}^{3}$種情況
綜合以上三種case，可以得出$f_7(3)=P_{1}^{4}+P_{2}^{3}+P_{2}^{3}=16$
---
<另解>純列舉
$X_7$的子集合中滿足$c(S)=3$的所有子集合$S$有$\{1,2,3,4\}、\{1,2,3,4,6\}、\{1,2,3,4,7\}、$
$\{2,3,4,5\}、\{2,3,4,5,7\}、\{3,4,5,6\}、\{1,3,4,5,6\}、$
$\{4,5,6,7\}、\{1,4,5,6,7\}、\{2,4,5,6,7\}、$
$\{1,2,3,5,6\}、\{1,2,3,6,7\}、\{2,3,4,6,7\}、$
$\{1,2,4,5,6\}、\{1,2,5,6,7\}、\{2,3,5,6,7\}、$，共16個
故$f_7(3)=16$
:::
### Problem 5
試求$f_{12}(0)$的值，並請說明理由。(含有空集合)
:::spoiler :cold_sweat: Hint:寫出一般式
觀察此題小case，並嘗試看出遞迴關係式(費式數列)
若今天欲求$f_{n}(0)$的值，也就是$X_{n}=\{1,2,3,...,n\}$中滿足沒有相鄰數對的子集合，則可以分成以下兩種case討論：
(1)若子集合有選取到`1`，則表示子集合中一定不能有`2`，則子集合數量可以看做是$f_{n-2}(0)$，表示後面(n-2)個數字中的情況數
(2)若子集合沒有選取到`1`，則子集合數量可以看做是$f_{n-1}(0)$，表示後面(n-1)個數字中的情況數
綜合以上討論，則可以得出以下遞迴關係式：
$f_{n}(0)=f_{n-2}(0)+f_{n-1}(0)$
會發現其實這是一個費式數列的關係式。
這時候可以直接透過遞迴式，逐步推出$f_{12}(0)$的值。
$f_{1}(0)=2$、$f_{2}(0)=3$、$f_{3}(0)=5$、$f_{4}(0)=8$
$f_{5}(0)=13$、$f_{6}(0)=21$、$f_{7}(0)=34$、$f_{8}(0)=55$
$f_{9}(0)=89$、$f_{10}(0)=144$、$f_{11}(0)=233$、$f_{12}(0)=377$
---
<另解>求得一般式
已知遞迴式$f_{n}(0)=f_{n-2}(0)+f_{n-1}(0)$
則可以透過遞迴式寫出特徵方程式：
$r^{2}=r+1$
求得$r=\frac{1+\sqrt5}{2},\frac{1-\sqrt5}{2}$
則可以假設$f_{n}(0)=A(\frac{1+\sqrt5}{2})^n+B(\frac{1-\sqrt5}{2})^n$
列舉前兩項數值，$f_{1}(0)=2$、$f_{2}(0)=3$，得到$f_{0}(0)=1$，並代入上式解得A、B
$\left\{
\begin{matrix}
f_{0}(0)&=&1&=&A+B\\
f_{1}(0)&=&2&=&A(\frac{1+\sqrt5}{2})+B(\frac{1-\sqrt5}{2})
\end{matrix}
\right.$
解完聯立方程式後得出：
$\left\{
\begin{matrix}
A&=&\frac{5+3\sqrt5}{10}\\
B&=&\frac{5-3\sqrt5}{10}\\
\end{matrix}
\right.$
則一般式$f_{n}(0)=\frac{5+3\sqrt5}{10}(\frac{1+\sqrt5}{2})^n+\frac{5-3\sqrt5}{10}(\frac{1-\sqrt5}{2})^n$
$n=12$代入後得$f_{12}(0)=377$
:::
### Problem 6
對任意正整數n，試求$f_n(1)$的值，並請說明理由，並依所得結果求$f_{10}(1)$之值。
:::spoiler :cold_sweat: Hint:延伸前幾題結果
若要求$f_n(1)$，則先觀察相鄰數對是什麼
(1)若相鄰數對是$\{1,2\}$，則不可選`3`，剩下其他數字4~n的情況數可以看做$f_{n-3}(0)$。同理，若相鄰數對是$\{n-1,n\}$情況數也是$f_{n-3}(0)$。
(2)若相鄰數對不是$\{1,2\}$或$\{n-1,n\}$，假設為$\{k,k+1\}$，則不可選`k-1`和`k+2`，剩下其他數字的情況數可以看做$f_{n-4}(0)$，而這樣的相鄰數對共有n-3組。
接著代入上題的結果，得出$\begin{split}f_n(1)&=2[\frac{5+3\sqrt5}{10}(\frac{1+\sqrt5}{2})^{n-3}+\frac{5-3\sqrt5}{10}(\frac{1-\sqrt5}{2})^{n-3}]\\&+(n-3)[\frac{5+3\sqrt5}{10}(\frac{1+\sqrt5}{2})^{n-4}+\frac{5-3\sqrt5}{10}(\frac{1-\sqrt5}{2})^{n-4}]\end{split}$
:::
### Problem 7
對$X_5$的所有子集合$S$，試求$c(S)$值的總和，並請說明理由。
:::spoiler :cold_sweat: Hint:特殊分case
我們知道$c(S)$值其實就是兩個相鄰數字的組數，則我們可以利用這點來分case，也就是觀察每種相鄰數對出現在哪些子集合中。
(1)含有$\{1,2\}$的子集合
:::
### Problem 8
設正整數$n\ge2$。對$X_n$的所有子集合$S$，試求$c(S)$值的總和，並請說明理由。
:::spoiler :rage: Hint:換句話說
:::
### Problem 9
對$X_9$中至少4個元素的所有子集合$S$，試求$c(S)$值的總和，並請說明理由。
:::spoiler :rage: Hint:延伸上題的演算法
:::
### Problem 10
設正整數$n\ge k\ge2$。對$X$中恰有$k$個元素的所有子集合$S$，試求$c(S)$值的總和，並請說明理由。
:::spoiler :imp: Hint:綜合上題取值演算法
:::
Sign in with Wallet
Connect another wallet