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,\dots ,n)$ such that: - $a_0=0,a_1=1,a_k=n$, - $a_{i+1}-a_i\le 2$ for all $0\le i\le 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\to 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|\le 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\to A_n$ by partitioning every $w\in S\backslash S_1$ into parts of the form ( $m,m+2,m+3,\dots ,m+2k)$ or ( $m,m+2,m+3,\dots ,m+2k+1$ ) in which $k\ge 1$ and then $f$ changes each part by the following rule: $(m,m+2,m+3,\dots ,m+2k)\mapsto (m,m+1,m+2,m+4,m+6,\dots ,m+2k)$ and $(m,m+2,m+3,\dots ,m+2k+1)\mapsto (m,m+1,m+3,m+5,\dots ,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\forall w\in S\backslash S_1.$$ Hence, $S_1\cap f\left(S\backslash S_1\right)=\varnothing$. 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)|\le |A_n|=F_n$$