Team selection tests for IMO 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,\dots ,S_{k-1}$ as the subsets of $\{1,2,3,\dots ,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=\lceil \frac{1000-t}{k}\rceil$. - Since $a_i=i\pm k$ and $a_i\equiv i(\mathrm{mod}k)$, two numbers $a_i$ and $i$ belong to same subset.

Denote $t=x_1<x_2<\dots <x_{m_t}$ as elements of $S_t$ then they form an arithmetic progression with formula $x_i=t+(i-1)k$ for $1\le i\le m_t$.

Put $y_i=a_{x_i}$ for $1\le i\le m_t$ then $\left|y_i-x_i\right|=\left|a_{x_i}-x_i\right|=k$ which implies that $y_1<y_2<\dots <y_{m_t}$ is a permutation of $x_1<x_2<\dots <x_{m_t}$.

Set $r_i=\frac{x_i-t}{k}+1$, $s_i=\frac{y_i-t}{k}+1$ for $1\le i\le 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,\dots ,k-1$, we have $m_0\le m_1\le \dots \le m_{k-1}$ are all even and $$m_0-m_{k-1}=\left[\frac{1000}{k}\right]-\left[\frac{1000-(k-1)}{k}\right]\le 1.$$ Hence, $m_0,m_1,\dots ,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$.