Let $n$ be a natural number and assume for a start that $n$ is divisible by $3$. Let $\sigma$ be a permutation of the set $\{1,2,\ldots, n\}$. I want to partition the vector $S=(\sigma(1),\sigma(2),\ldots, \sigma(n))$ into three vectors $(a\_1,\ldots, a\_{n/3})=A$, $(b\_1,\ldots, b\_{n/3})=B$ and $(c\_1,\ldots, c\_{n/3})=C$ of equal length. Because this is boring, I impose some restrictions. First, I don't want to have consecutive numbers in one vector, so for example $a\_i=3$, $a\_j=4$ for some $i,j$ is not allowed. Second, I require that for all $i$, $a\_i=\sigma(j)$ implies $|3i-j|\leq k$, where $k$ is some constant independent of $n$ (and the same for $B$ and $C$).


Consider the following example. If $\sigma$ is the identical permutation, I choose $A=(1,4,7,\ldots)$, $B=(2,5,8,\ldots)$, $C=(3,6,9,\ldots)$. Then for each vector every pair of components has distance $2$, and $A$, $B$ and $C$ have "uniform density", because I roughly "chose every third number".


The question is, whether there is $k$ such that the above construction is possible for all $n$ and $\sigma$.


The second question is, if partitioning into $3$ vectors fails, does it work for $4$ instead of $3$ or an even larger number?


NOTE: I set the graph-theory tag, because using graph theory seems like a reasonable approach to me.



Partitioning finite ordered sets
The answer to your question is yes with $k=2$.


I came up with a proof using the fact that the [Strong Chromatic Number](http://en.wikipedia.org/wiki/Strong_coloring) $(s{\chi})$ of a cycle of size multiple of $3$ is $3$ $( s\chi(C\_{3t}) = 3)$ see this [reference](http://www.lars-daniel.se/papers/3or4characterisation.pdf) for more details. 


The argument goes like this:


Let $C\_n$ be the standard cycle $(1, 2, 3, ...,n-1, n)$. Label the vertices of $C\_n$ as follows: 


Vertex $\rho(j)$ gets labeled with the integer $ \lfloor \frac{j+2}{3} \rfloor$ (it comes from the second requirement). 


Notes that the labels come from the set {1, 2, 3, ..., $\frac{n}{3}$} and that the labeling partition the vertices into $\frac{n}{3}$ parts each of size $3$.


Since $s\chi(C\_{n}) = 3$, there is a proper $3$-coloring of $C\_n$ such that vertices with the same label get different colors. The coloring gives the three different vectors and the labeling define the indices for the vectors. 


