Is there an $11$-element circular permutation of $\{1,2,...,12\}$ with all $|a_i-a_{i+1}|$ distinct?

Question

Can you choose $11$ different numbers among them so that the numbers $|a_1-a_2|, |a_2-a_3|,\ldots,|a_{10}-a_{11}|,|a_{11}-a_{1}|$ are all different. The smartest thing that my dumbest mind could accomplish is that all those differences are $1,2,3,...,11$. From this, there are two ways - construct an example which is quite painful - but I did it for $n=4,5$ and tried for $6$ so I couldn't find example for $3$, so may be there something about $6$ and its multiplicators? another way - prove by something, may be algebra or properties of numbers of $1,2,3,\ldots,11$ (sum of squares so we could get rid of modulus), try to prove that there always will be at least two equal differences and so on. Can you give me some hint?

Answer 1

I haven't been able to do this by any reasonable method. I worked out that the sum of the numbers that are bigger than both their neighbors (considering the numbers as arranged on a circle) minus the sum of the numbers that are smaller than both their neighbors must be $33,$ but I wasn't able to turn that to account.

I started to do it by brute force, but I was afraid of making a mistake, so I wrote a simple-minded python script to do it. I figured it would take longer to write an intelligent script than it would to write and run the dumb one.

I also listed the elements that were larger than both of their neighbors and the elements smaller than both their neighbors. In all cases there were $5$ of each. I don't know what, if anything can be made of that.

There are $208$ solutions.

Here's the script

from itertools import permutations

N = 12

def uniqueDiffs(x):
    y = x+(x[0],)

    a = [abs(y[t]-y[(t+1)]) for t in range(N-1)]
    return len(set(a))==N-1

def minors(x):
    y = (x[-1],) + x + (x[0],)
    return sorted([y[i] for i in range(1,N) if y[i-1] > y[i] < y[i+1]])

def majors(x):
    y = (x[-1],) + x + (x[0],)
    return sorted([y[i] for i in range(1,N) if y[i-1] < y[i] > y[i+1]])

good = []

S= range(1,N+1)
start = (1,N)
S = set(range(2,N))
for x in S:
    T=S.copy()
    T.remove(x)
    for p in permutations(T):
        s = start + p
        if uniqueDiffs(s):
            good.append(s)

print(len(good), "solutions")
for g in good:
    print(g, minors(g), majors(g))

Here's the first solution it printed

(1, 12, 2, 7, 8, 6, 9, 5, 11, 3, 10)

I don't imagine anyone wants to see the other $207.$

P.S.

I got to wondering what values other than $12$ work. The problem makes no sense for $N<4.$ I tested for $4\le N\le13$ and found that there are solutions only for $N=4,5,8,9,12,13.$ Also, in all cases the number of elements larger than both their neighbors ("majors") is the same as the number of elements smaller than both their neighbors ("minors"), but this number is not necessarily the same in all solutions. For $N=13,$ there are solution with $5$ majors and $5$ minors, and also solutions with $6$ of each. It is of course, tempting to guess that the problem can be solved only when $N\equiv0\pmod{4}$ or $N\equiv1\pmod{4},$ but I have far too little data. I will have to write a more intelligent program before trying to test larger cases.

P.P.S

By considering the difference of the majors and the minrs it's easy to show that the problem is impossible when $N\equiv2\pmod{4}$ or $N\equiv3\pmod{4}$

Answer 2

@Saulspatz has shown an example but I've found a methodical approach to finding one that could be done by hand in a few minutes to give you an answer in a competition. It could also be easily computerised.

Start by laying out a grid with columns, $D=1,2,\ldots11$, representing the particular differences you can have between successive elements in a circular permutation. Then lay out the rows, $B=12,11,\ldots1$ and entries $A$, representing successive pairs of elements which would give you the particular $B-A=D$. Then do this again for another $B=12,11,\ldots1$ but representing the successive pairs of elements that give you $B-A=-D$. It should look like the following figure.

I'll be highlighting chosen cells in yellow, and highlighting impossible cells in red. Now we can introduce the rules. We want one of each $D$, so each column needs exactly $1$ yellow. No $B$ can be followed by more than one $A$ (but must be followed by something) so exactly one yellow per row. No $A$ can follow more than one $B$ so once an $A$ is highlighted, all other equal $A$'s are removed from the grid. We are also only picking $11$ elements so we have to remove all $B$'s and $A$'s for a particular number (I've chosen $6$). Let's begin by removing all $B=6$ rows and $A=6$ cells.

Since there are multiple choices that thin out at the right, I'll be going for the topmost possible cell while moving left to right. We can then pick the cell $B=12,A=1$ such that $D=11$. This means we have to remove all other $B=12$'s, all $A=1$'s and all $D=11$'s. Hence:

We can continue with this approach and generate the sequences:

$$\begin{aligned}(&12,1)\\(2,&12,1)\\(11,2,&12,1)\\(3,11,2,&12,1)\\(10,3,11,2,&12,1)\\(4,10,3,11,2,&12,1)\\(9,4,10,3,11,2,&12,1)\end{aligned}$$

But now we run into a slight problem shown in the next figure. After we've chosen that $4$ follows $9$, we're left with the following chart. For $D=4$, if we pick $B=5$, $A=9$, we will have to remove $B=1$, $A=5$ since it is also $D=4$. In which case we will fail, since we will have no cell for $B=1$. Hence, we must pick $B=1$, $A=5$.

We can then proceed as normal and get the following chart. This gives us the sequence $(9,4,10,3,11,2,12,1,5,8,7)$, which proves the result.