Arrange all numbers from 1 to n such that no 3 of them are in Arithmetic Progression

Is there any possible arrangement of numbers all from $1$ to $n$ such that in the resultant array of numbers, no subsequence of length $3$ is in Arithmetic Progression. For example, in $1,3,2,4,5$, there is a subsequence of length $3$ that is in AP, that is, $1,3,5.$ But in $1,5,3,2,4$ there is no subsequence of length $3.$ I am trying to find a possible arrangement for larger values of $n,$ but unable to do so.

Solution 1:

These exist for all lengths. One quick construction to find arbitrarily large permutations with this property is to go from a length-$n$ permutation $(a_1, a_2, \dots, a_n)$ which has the property to the length-$2n$ permutation $(2a_1, 2a_2,\dots,2a_n, 2a_1-1, 2a_2-1, \dots, 2a_n-1)$. For example, we go from $$(1,2)$$ to $$(2,4,1,3)$$ to $$(4,8,2,6,3,7,1,5)$$ to $$(8,16,4,12,6,14,2,10,7,15,3,11,5,13,1,9)$$ and so on.

(If you want an example with a length that's not a power of $2$, just drop some of the largest terms of one of the permutations.)

To see that this always works, note that an arithmetic progression has the form $(x, \frac{x+y}{2}, y)$; for $\frac{x+y}{2}$ to be an integer, $x$ and $y$ must be both even or both odd. In the construction above, when $x$ and $y$ are both even, they are both in the first half of the bigger permutation; when $x$ and $y$ are both odd, they are both in the second half of the bigger permutation. In either case, they cannot be the endpoints of an arithmetic progression, because then $\lceil \frac x2\rceil$ and $\lceil \frac y2\rceil$ would be the endpoints of an arithmetic progression in $(a_1, a_2, \dots,a_n)$.

But there are many more solutions: see https://oeis.org/A003407 for a count.

Solution 2:

Here are the ones for $n=6$:

(1, 5, 3, 2, 6, 4)
(1, 5, 3, 4, 2, 6)
(1, 5, 3, 4, 6, 2)
(1, 5, 3, 6, 2, 4)
(1, 5, 6, 3, 2, 4)
(2, 1, 6, 4, 5, 3)
(2, 6, 1, 4, 5, 3)
(2, 6, 4, 1, 5, 3)
(2, 6, 4, 3, 1, 5)
(2, 6, 4, 3, 5, 1)
(2, 6, 4, 5, 1, 3)
(3, 1, 2, 5, 6, 4)
(3, 1, 5, 2, 6, 4)
(3, 1, 5, 4, 2, 6)
(3, 1, 5, 4, 6, 2)
(3, 1, 5, 6, 2, 4)
(3, 5, 1, 2, 6, 4)
(3, 5, 1, 4, 2, 6)
(3, 5, 1, 4, 6, 2)
(3, 5, 1, 6, 2, 4)
(3, 5, 4, 1, 2, 6)
(3, 5, 4, 1, 6, 2)
(3, 5, 4, 6, 1, 2)
(3, 5, 6, 1, 2, 4)
(4, 2, 1, 6, 5, 3)
(4, 2, 3, 1, 6, 5)
(4, 2, 3, 6, 1, 5)
(4, 2, 3, 6, 5, 1)
(4, 2, 6, 1, 5, 3)
(4, 2, 6, 3, 1, 5)
(4, 2, 6, 3, 5, 1)
(4, 2, 6, 5, 1, 3)
(4, 6, 2, 1, 5, 3)
(4, 6, 2, 3, 1, 5)
(4, 6, 2, 3, 5, 1)
(4, 6, 2, 5, 1, 3)
(4, 6, 5, 2, 1, 3)
(5, 1, 3, 2, 6, 4)
(5, 1, 3, 4, 2, 6)
(5, 1, 3, 4, 6, 2)
(5, 1, 3, 6, 2, 4)
(5, 1, 6, 3, 2, 4)
(5, 6, 1, 3, 2, 4)
(6, 2, 1, 4, 5, 3)
(6, 2, 4, 1, 5, 3)
(6, 2, 4, 3, 1, 5)
(6, 2, 4, 3, 5, 1)
(6, 2, 4, 5, 1, 3)