Saudi Arabian Mathematical Competitions

Firstly, denote by $A_{n}$ the set of all sub-sequences $\left(a_{i}\right)_{i=0}^{k}$ of $(0,1,2, \ldots, n)$ such that:
- $a_{0}=0, a_{1}=1, a_{k}=n$,
- $a_{i+1}-a_{i} \leq 2$ for all $0 \leq i \leq k-1$.
Obviously, $A_{n}$ is one of the sets $S$ satisfying Conditions i)-ii).
It is also clear that $|A_{1}|=|A_{2}|=1$.
If $n>2$, then for each $\left(a_{i}\right)_{i=0}^{k} \in A_{n}$, let us define $F\left(\left(a_{i}\right)_{i=0}^{k}\right)=\left(a_{i}\right)_{i=0}^{k-1}$. In so doing, we have clearly obtained a bijection $F: A_{n} \rightarrow A_{n-1} \cup A_{n-2}$, hence,
$$|A_{n}|=|A_{n-1}|+|A_{n-2}|$$
when $n>2$. So, $|A_{n}|$ is the $n^{\text{th}}$ Fibonacci number, which is denoted by $F_{n}$. We will show that $F_{n}$ is the maximum value of $|S|$, among all the sets $S$ satisfying Conditions i)-ii). Indeed, for such a set $S$, we need only prove that
$$|S| \leq F_{n} .$$
Let $S_{1}=S \cap A_{n}$. Then $S=S_{1} \cup\left(S \backslash S_{1}\right)$. We define a mapping $f: S \backslash S_{1} \rightarrow A_{n}$ by partitioning every $w \in S \backslash S_{1}$ into parts of the form ( $m, m+2, m+3, \ldots, m+2k)$ or ( $m, m+2, m+3, \ldots, m+2k+1$ ) in which $k \geq 1$ and then $f$ changes each part by the following rule:
$(m, m+2, m+3, \ldots, m+2k) \mapsto (m, m+1, m+2, m+4, m+6, \ldots, m+2k)$
and
$(m, m+2, m+3, \ldots, m+2k+1) \mapsto (m, m+1, m+3, m+5, \ldots, m+2k+1)$.
We can see that:
- $f$ is one-to-one.
- The two sequences $w$ and $f(w)$ do not satisfy Condition ii); so,
$$f(w) \notin S \quad \forall w \in S \backslash S_{1} .$$
Hence, $S_{1} \cap f\left(S \backslash S_{1}\right)=\emptyset$. Since $S_{1} \cup f\left(S \backslash S_{1}\right) \subset A_{n}$, it follows that
$$|S|=|S_{1} \cup f\left(S \backslash S_{1}\right)| \leq |A_{n}|=F_{n}$$