Question 16
Let $n \geq 1$ be a fixed positive integer. We consider all the sets $S$ which consist of sub-sequences of the sequence $0,1,2, \ldots, n$ satisfying the following conditions:
i) If $\left(a_{i}\right)_{i=0}^{k}$ belongs to $S$, then $a_{0}=0, a_{k}=n$ and $a_{i+1}-a_{i} \leq 2$ for all $0 \leq i \leq k-1$.
ii) If $\left(a_{i}\right)_{i=0}^{k}$ and $\left(b_{j}\right)_{j=0}^{h}$ both belong to $S$, then there exist $0 \leq i_{0} \leq k-1$ and $0 \leq j_{0} \leq h-1$ such that $a_{i_{0}}=b_{j_{0}}$ and $a_{i_{0}+1}=b_{j_{0}+1}$.
Find the maximum value of $|S|$ (among all the above-mentioned sets $S$ ).
i) If $\left(a_{i}\right)_{i=0}^{k}$ belongs to $S$, then $a_{0}=0, a_{k}=n$ and $a_{i+1}-a_{i} \leq 2$ for all $0 \leq i \leq k-1$.
ii) If $\left(a_{i}\right)_{i=0}^{k}$ and $\left(b_{j}\right)_{j=0}^{h}$ both belong to $S$, then there exist $0 \leq i_{0} \leq k-1$ and $0 \leq j_{0} \leq h-1$ such that $a_{i_{0}}=b_{j_{0}}$ and $a_{i_{0}+1}=b_{j_{0}+1}$.
Find the maximum value of $|S|$ (among all the above-mentioned sets $S$ ).