Saudi Arabian Mathematical Competitions

For each positive integer $n \geq 1$, we denote $s_{n}$ as the number of permutations of the first $n$ positive integers that satisfy the condition
$$a_{i+1}-a_{i} \leq 1, \quad i=1,2,\ldots,n-1.$$
We call these permutations "nice".

First, we shall prove that $s_{n}=2^{n-1}$ for all $n \geq 1$.
Let $k$ be the index such that $a_{k}=n$. We have $a_{k-1} \geq a_{k}-1=n-1$ which implies that $a_{k-1}=n-1$, and so on, we have $a_{1}=n-k+1$.
All numbers after $a_{k}$ are $1,2,3, \ldots, n-k$ forming a nice permutation, so in case $a_{k}=n$, the number of nice permutations is $s_{n-k}$.
Note that if $k=n$, we have only $1$ nice permutation: $1,2,3,\ldots,n$.
Therefore, we get the following formula:
$$s_{n}=1+\sum_{k=1}^{n-1} s_{n-k}=s_{1}+s_{2}+\ldots+s_{n-1}+1$$
It is easy to compute $s_{1}=1$, $s_{2}=2$, then by induction, we have $s_{n}=2^{n-1}$ for all $n \geq 1$.

Back to the original problem, we suppose that $a_{i}=i$ and $a_{j}=j$. Thus,
$$a_{i+1} \leq a_{i}+1=i+1, \quad a_{i+2} \leq a_{i+1}+1 \leq i+2$$
and so on, then we have $a_{j} \leq j$. But in fact, $a_{j}=j$ which implies that the equality must occur.
So $a_{k}=k$ for all $k=i, i+1, i+2, \ldots, j$. But there are only $2$ indices $i, j$ like that so we have $j=i+1$.

Continue, $a_{i-1} \geq a_{i}-1=i-1$, but $a_{i}=i$, $a_{i+1}=i+1$ so $a_{i-1} \geq i+2$. Then,
$$a_{i-2} \geq a_{i-1}-1 \geq i+1 \text{ or } a_{i-2} \geq i+2.$$
By the same way, it is clear to check that $a_{1}, a_{2}, \ldots, a_{i-1} \geq i+2$. Similarly, we also have $a_{i+2}, a_{i+3}, \ldots, a_{2016} \leq i-1$.
Therefore, the lengths of the two sequences $a_{1}, a_{2}, \ldots, a_{i-1}$ and $a_{i+2}, a_{i+3}, \ldots, a_{2016}$ are the same. Hence,
$$i-1=2015-i \Leftrightarrow i=1008.$$
So the given nice permutation looks like
$$\left(a_{1}, a_{2}, \ldots, a_{1007}, 1008, 1009, a_{1010}, a_{1011}, \ldots, a_{2016}\right).$$
Clearly, the subsequence $\left(a_{1010}, a_{1011}, \ldots, a_{2016}\right)$ forms a nice permutation of length $1007$ and the same with the subsequence
$$\left(a_{1}-1009, a_{2}-1009, \ldots, a_{1007}-1009\right).$$
Therefore, the number of permutations satisfying the given condition is
$$s_{1007} \cdot s_{1007}=\left(2^{1006}\right)^{2}=2^{2012}.$$ $\square$