Conserving contiguity with a transposed progression

[Loren Booda]

Can a sequence of integers from 1 to N be rearranged so that no two neighbors retain their original adjacency?

 

[dodo]

I suppose running it backwards (6,5,4,3,2,1) is not enough for what you meant.

Then, how about 1,3,5,2,4,6.

 

[Loren Booda]

And for any N?

 

[dodo]

Well, for N <= 3 you obviously can't, so the trivial response is "no".

For N >= 5 you only need to list the odds, then the evens.

The interesting case is N=4. If you don't count the endpoints, 2,4,1,3 suffices. If you count them as neighbors, then
- Sequences starting with "1" won't have a place for "2": second and fourth are neighbors to "1", and third place would make it neighbor to wherever you place "3".
- Similar for sequences starting with "4": there's no place for "3" (third place leaves no place for "2").
- Similar when starting with "2", where there is no place for "3" (second and fourth are neighbors to "2", third would leave no place for "4").
- And same for starting with "3", where similarly there is no place for "2" (third place leaves no place for "1").
So with wrap-around, N=4 is a no-no.