Arrangements of $1,1,2,2,\ldots,n,n$ with $i$ numbers between each pair of $i$-s

Question

For which $n$ it is possible to arrange the integers $1$, $1$, $2$, $2$, $\ldots$, $n$, $n$ in some order such that for all $i=1,2,\ldots,n$ between the two copies of $i$ there are exactly $i$ numbers?

This problem arose from a discussion with a friend. We have no idea about $n\equiv 0, 3 \pmod 4$ (apart from that it works up to $n=7$ or maybe $n=8$) but here is a proof that $n\equiv 1,2\pmod 4$ are not possible.

If the arrangement is $a_1 \ a_2 \ a_3 \dots a_{2n}$, put a comma between each two consecutive $a_i$-s. We double-count the number of pairs $(i, \mbox{comma})$ where the comma lies somewhere between the two copies of $i$. On one hand, there are $i$ numbers between the two $i$-s and hence $i+1$ commas, so overall the number of pairs is $2 + 3 + \cdots + n + (n+1) = \frac{n(n+3)}{2}$. On the other hand, there are $2n-1$ commas, so say that there are $n$ in odd positions and $n-1$ in even positions - each comma in odd position has an odd number of pairs around it and each comma in even position has an even number of pairs around it (to see this, start from the first comma which has $1$ pair and observe that each one after changes its number of pairs by $1$, up or down), so the overall amount of pairs has the same parity as $n$. In particular, $\frac{n(n+3)}{2} \equiv n \pmod 2$, i.e. $n^2 + n \equiv 0 \pmod 4$, which does not hold for $n\equiv 1,2 \pmod 4$.

Ideas on how could one proceed (constructively?) for $n\equiv 0,3 \pmod 4$? Any help appreciated!

Answer 1

I can prove there are infinitely many $n$ for which there are solutions.

Specifically, if we have a solition for $n,$ we can get a solution to $n'=3n+3.$

We will do so by proving that there is a sequence of length $4n+6$ of pairs of numbers from $n+1$ to $3n+3$ which satisfy your property.

We start with the sequence $$(2n+2,2n+3,\dots,3n+3,n+1,\dots,2n+1)$$ This entirely determine the rest of the sequence.

For example, $n=3$ then we get a complete example:

$$(8,9,10,11,12,4,5,6,7,\\8,4,9,5,10,6,11,7,12)$$

The second half is the alternating interlaced sequence of the $(8,9,10,11,12)$ and $(4,5,6,7).$

So if we can solve for $n,$ we can append the solution to this and get a solution for $3n+3.$

Since we have solutions for $n=3,$ we have solutions for $12,$ so we have solutions for $39,$ so we have solutions for $120,$ etc. We have a way to create solutions for infinitely many $n.$

---

It seems, from some Python scripting experiments, that if $N\equiv 0,3\pmod 4$ and $n$ is the largest integer $\equiv 0,3\pmod 4$ with $3n+3\leq N,$ there is an answer for $N$ beginning with an answer for $n.$ But I've only shown the above case, where $3n+3=N,$ which is when $N\equiv 0,3\pmod {12}.$

But you might be able to do something similar, likely a little more complex, for $N\equiv 4,7,8,11\pmod{12}.$

---

A different way of deriving that $n\equiv 0,3\pmod 4$ requirement. And maybe an explanation why the other cases are hard.

We are going to view a circular version of the problem. If there is an answer to your problem, there is an answer to the circular problem, but not vice versa.

If we have the cyclic group $G=\mathbb Z/2n\mathbb Z$ we are seeking seeking distinct elements $c_1,\dots, c_n$ such that $c_i+i+1\neq c_j$ and $c_i+i+1\neq c_j+j+1$ for any $i\neq j.$

Then $$\sum_i(2c_i+i+1)=\frac{n(n+3)}2+2\sum c_i\equiv \sum_{k=0}^{2n-1} k=n(2n-1)\equiv n\pmod {2n}$$

This means $\frac{n(n+3)}{2}$ and $n$ must have the same parity, so $\frac{n(n+1)}{2}$ must be even, so we get your result that $n\equiv0,3\pmod 4.$

So you can't solve this problem when $n\equiv 2,3$ even if we allow more freedom of a circular set of pairings.

We also get, when $n\equiv 0,3\pmod 4$ that:

$$\sum c_i\equiv -\frac{n(n+1)}{4}\pmod{n}$$

When $n\equiv 0\pmod 4,$ that means $\sum c_i\equiv -\frac n4\pmod n.$

When $n\equiv 3\pmod 4,$ we get $\sum c_i\equiv 0\pmod n.$

---

The uniqueness condition is equivalent to requiring $c_i-c_j\neq 0,-(i+1), j+1, j-i.$

---

I would not be surprised if there was always a circular case for $n\equiv 0,3,$ but that sometimes there is no non-circular case. That would explain why it is hard to prove relatively quickly.

---

For example, if, rather than $i$ between the two $i$s, we required $f_i$ between them, then we'd need $\sum f_i$ to be even.

But when all $f_i=2,$ we can solve the circular case for any $n>1,$ but we can only solve the non-circular case when $n$ is a multiple of $3.$

---

Actually, even in the straight question, if $c_i$ is the position of the left-most $i,$ where the positions are labeled $0,1,\dots,2n-1,$ then you get:

$$n+\frac{n(n+1)}{2}+2\sum c_i = n(2n-1)$$ or $$\sum c_i =n^2-n-\frac{n(n+1)}{4}=\frac{n(3n-5)}{4}.$$

Using this, by hand, I got an example when $n=7:$

$$57263254376141$$

And here is an answer for $n=8:$

$$2672485364735181$$