SAUDI ARABIAN MATHEMATICAL COMPETITIONS

For each positive integer $n\ge 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\le 1,i=1,2,\dots ,n-1.$$ We call these permutations "nice".

First, we shall prove that $s_n=2^{n-1}$ for all $n\ge 1$. Let $k$ be the index such that $a_k=n$. We have $a_{k-1}\ge 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,\dots ,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,\dots ,n$. Therefore, we get the following formula: $$s_n=1+\sum _{k=1}^{n-1}{s}_{n-k}=s_1+s_2+\dots +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\ge 1$.

Back to the original problem, we suppose that $a_i=i$ and $a_j=j$. Thus, $$a_{i+1}\le a_i+1=i+1,a_{i+2}\le a_{i+1}+1\le i+2$$ and so on, then we have $a_j\le 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,\dots ,j$. But there are only $2$ indices $i,j$ like that so we have $j=i+1$.

Continue, $a_{i-1}\ge a_i-1=i-1$, but $a_i=i$, $a_{i+1}=i+1$ so $a_{i-1}\ge i+2$. Then, $$a_{i-2}\ge a_{i-1}-1\ge i+1\text{ or }{a}_{i-2}\ge i+2.$$ By the same way, it is clear to check that $a_1,a_2,\dots ,a_{i-1}\ge i+2$. Similarly, we also have $a_{i+2},a_{i+3},\dots ,a_{2016}\le i-1$. Therefore, the lengths of the two sequences $a_1,a_2,\dots ,a_{i-1}$ and $a_{i+2},a_{i+3},\dots ,a_{2016}$ are the same. Hence, $$i-1=2015-i\iff i=1008.$$ So the given nice permutation looks like $$\left(a_1,a_2,\dots ,a_{1007},1008,1009,a_{1010},a_{1011},\dots ,a_{2016}\right).$$ Clearly, the subsequence $\left(a_{1010},a_{1011},\dots ,a_{2016}\right)$ forms a nice permutation of length $1007$ and the same with the subsequence $$\left(a_1-1009,a_2-1009,\dots ,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$