, 2018

Note that $k=1$ is an answer since we can choose a permutation with $a_{2i-1}=2i$, $a_{2i}=2i-1$.

Now we take $k>1$, denote $S_{0}, S_{1}, S_{2}, \ldots, S_{k-1}$ as the subsets of $\{1,2,3, \ldots, 1000\}$ and all elements of $S_{i}$ are congruent to $i$ modulo $k$. We have:
- The number of elements of $S_{t}$ is $m_{t}=\left\lceil\frac{1000-t}{k}\right\rceil$.
- Since $a_{i}=i \pm k$ and $a_{i} \equiv i \pmod{k}$, two numbers $a_{i}$ and $i$ belong to same subset.

Denote $t=x_{1}<x_{2}<\ldots<x_{m_{t}}$ as elements of $S_{t}$ then they form an arithmetic progression with formula $x_{i}=t+(i-1)k$ for $1 \leq i \leq m_{t}$.

Put $y_{i}=a_{x_{i}}$ for $1 \leq i \leq m_{t}$ then $\left|y_{i}-x_{i}\right|=\left|a_{x_{i}}-x_{i}\right|=k$ which implies that $y_{1}<y_{2}<\ldots<y_{m_{t}}$ is a permutation of $x_{1}<x_{2}<\ldots<x_{m_{t}}$.

Set $r_{i}=\frac{x_{i}-t}{k}+1$, $s_{i}=\frac{y_{i}-t}{k}+1$ for $1 \leq i \leq m_{t}$ then $r_{i}=i$ and $\left|s_{i}-i\right|=1$.

We have
$$\sum_{i=1}^{m_{t}}\left|r_{i}-s_{i}\right|+\sum_{i=1}^{m_{t}}\left|r_{i}+s_{i}\right|=2 \sum_{i=1}^{m_{t}} \max \{r_{i}, s_{i}\}$$
so $m_{t}+2 \sum_{i=1}^{m_{t}} r_{i}=2 \sum_{i=1}^{m_{t}} \max \{r_{i}, s_{i}\}$ and $m_{t}$ is even. By the similar definition for $i=0,1, \ldots, k-1$, we have $m_{0} \leq m_{1} \leq \ldots \leq m_{k-1}$ are all even and
$$m_{0}-m_{k-1}=\left[\frac{1000}{k}\right]-\left[\frac{1000-(k-1)}{k}\right] \leq 1 .$$
Hence, $m_{0}, m_{1}, \ldots, m_{k-1}$ are all equal and even. This can happen when $k \mid 1000$ and $\frac{1000}{k}$ is an even number. It is easy to check that we can construct such a permutation satisfying these $k$.

Therefore, $k$ is a divisor of $500$.