Consider a bipartite graph $G=(A,B,E)$ with $1,2,3, \ldots ,1000$ are the vertices in $A$, $a_1,a_2, \ldots , a_{1000}$ are the vertices in $B$, $2$ vertices $m,a_m$ are connected iff $ |m-a_m |=k$ Now consider the first $k$ numbers $1,2,3, \ldots , k$, then the motivation can be easily see from this illustration (Since $1$ can only be connected to $k+1$, $2$ can only be connected to $k+2$ and so on...) Thus since $k$ is a positive integers, the bipartite graph is divided into some connected sub-bipartite graph with $2k$ vertices in each partition in each subgraph, which means $2k \mid 1000$ or $k \mid 500$ is the solution!