SAUDI ARABIAN MATHEMATICAL COMPETITIONS

1) First, replace $2015$ and $2016$ by $3$ and $4$ respectively for convenience. We consider the permutation of $\{1,2,3,\dots ,7\}$ as follows: $$1,5,2,6,3,7,4.$$ The numbers increase by $4$ and decrease by $3$, then the sequence covers all numbers from $1$ to $7$. Add $1$ to each term of the above sequence, we get $$8,12,9,13,10,14,11.$$ Combine two sequences, we have $$1,5,2,6,3,7,4,8,12,9,13,10,14,11.$$ This is another permutation of $\{1,2,3,\dots ,14\}$. By this method, we can construct the desired permutation for each number of the form $7k$, $k\in \mathbb{Z}$, satisfying the condition.

In the same way with the two given numbers $2015$ and $2016$: $$1,1+2016,1+2016-2015,\dots$$ Increase by $2016$ then decrease by $2015$ and so on, we can get the desired permutation for each number of the form $(2015+2016)k$, $k\in \mathbb{Z}$.

2) Now it is easy to see that all numbers $k$ such that $\gcd (k,2016)>1$ do not satisfy the given condition. Indeed,

Suppose that $\gcd (k,2016)=d>1$ and there exists a number $n$ such that the permutation of $\{1,2,3,\dots ,n\}$ satisfies the given condition. Then all numbers in this sequence have the same remainder when divided by $d$, which is a contradiction.

Now we will show that every number coprime with $2016$ will satisfy the given condition by proving the general statement:

If $m,k$ are two positive numbers and $\gcd (m,k)=1$, then there are infinitely many numbers $n$ such that there exists a permutation with the property that the difference between any two adjacent numbers is equal to either $m$ or $k$.

Suppose that $m>k$ and $m=ak+b$, $0\le b\le k-1$. We will prove that each number $n$ which is a multiple of $t(m+k)=(a+1)k+b$ satisfies the given condition. Indeed,

Partition the set $\{1,2,3,\dots ,n\}$ into $k$ sets and each set contains the numbers sharing the same remainder when divided by $k$. And each of them will be arranged decreasing from the largest to the smallest (except the set containing number $1$). $$\begin{array}{rl}& 1\to 1+(ak+b)\to 1+(a-1)k+b\to \dots \to 1+b\to \dots \\ & 1+ak+2b\to 1+(a-1)k+2b\to \dots \to 1+2b\to \dots \\ & \dots \\ & 1+ak+(k-1)b\to 1+(a-1)k+(k-1)b\to \dots \to 1+(k-1)b\to \dots \end{array}$$ It is easy to see that the difference between two adjacent numbers in each sequence is $k$ and two sequences can be connected by adding the smallest number in one set to the biggest number in another set. Notice that when we take a number $i\in \{2,3,4,\dots ,k\}$ and add $m$, we get $i+m$ which has the remainder differing from $i$ when divided by $k$ and since $\gcd (m,k)=1$ then the set $$\{i,i+m,i+2m,\dots ,i+(k-1)m\}$$ forms a complete system of residues modulo $k$, then when we connect all sets we get the permutation of $\{1,2,3,\dots ,n\}$. $\square$