I came across this problem more than 2 years ago when Pranave, a
colleague at RSA, posted this in the
internal mathematics forum.

Given a list of first n natural numbers with each natural number
occurring exactly twice in the list, we need to arrange the list in a
manner such that there are exactly k numbers between two k's for each k
in the sequence.

For a small list, say, (1, 1, 2, 2, 3, 3, 4, 4), the answer can be
obtained by trial and error: (4, 1, 3, 1, 2, 4, 3, 2).

But what if the list is very long? There is another important question:
Is there a solution for every possible such list? The answer turns out
to be: No. One can easily see that there is no valid arrangements for
(1, 1) or (1, 1, 2, 2) that satisfy the condition specified in the
problem statement.

So, we have two things to solve now.

- For what values of n is the problem solvable?
- If the problem is solvable for some value of n, how do we solve it?

In this blog post, I'll show how I solved it. I took some help from the
computer by writing a Python
program to see if I could notice any patterns. Here is the output.

n = 1 : 0 solutions ( 0 s)
n = 2 : 0 solutions ( 0 s)
n = 3 : 2 solutions ( 0 s)
n = 4 : 2 solutions ( 0 s)
n = 5 : 0 solutions ( 0 s)
n = 6 : 0 solutions ( 0 s)
n = 7 : 52 solutions ( 0 s)
n = 8 : 300 solutions ( 0 s)
n = 9 : 0 solutions ( 1 s)
n = 10 : 0 solutions ( 6 s)
n = 11 : 35584 solutions ( 45 s)
n = 12 : 216288 solutions ( 390 s)

From the output, I could form a conjecture:

There exists a permutation of (1, 1, 2, 2, …, n, n) such that for
each k in the sequence (1 ≤ k ≤ n) there are k numbers between the
two k's if and only if n ≡ 3 (mod 4) or n ≡ 0 (mod 4).

Let me show how I proved this conjecture.

### Proof of the necessity of the condition n ≡ 3 (mod 4) or n
≡ 0 (mod 4)

Let (1, 1, 2, 2, …, n, n) be a sequence which can be rearranged
such that there are k numbers between the two k's for each k in the
sequence. Let us number the position of each number in this permutation
as 1, 2, …, 2n.

Partition the numbers in this partition into two halves:

- Partition 1: All numbers in odd numbered positions.
- Partition 2: All numbers in even numbered positions.

The length of each partition is n.

Note that if k (1 ≤ k ≤ n) is even, one of the
two k's is located on an odd numbered position and the other one on even
numbered position.

If k is odd the two k's are both located on odd numbered positions or
both located on even numbered positions. The two k's will never be split
in two different partitions. It will be together in one partition.

From the above discussion it is obvious that the number of even numbers
in each partition is equal. Let the number of even numbers in each
partition be m. Let us assume there are p pairs of odd numbers in
partition 1 and q pairs of odd numbers in partition 2. Thus, there are
2p odd numbers in partition 1 and 2q odd numbers in partition 2.

Since, the length of each partition is n, n = m + 2p
= m + 2q. Hence, p = q. This implies that there must
be p + q = 2p pairs of odd numbers in the two
partitions, i.e. the number of positive odd numbers less than or equal
to n is 2p.

In other words, the number of positive odd numbers less than or equal to
n must be even. **… (1)**

We know that, for a positive integer n, the number of positive odd
numbers less than or equal to n is ⌈n/2⌉. Let q be the
quotient and r be the remainder obtained after dividing n by 4. We have
four possible cases.

- If n = 4q + 1, number of positive odd numbers less than or equal
to n is, ⌈(4q + 1)/2⌉ = 2q + 1.
- If n = 4q + 2,
number of positive odd numbers less than or equal to n is, ⌈(4q +
2)/2⌉ = 2q + 1.
- If n = 4q + 3, number of positive odd
numbers less than or equal to n is, ⌈(4q + 3)/2⌉ = 2q +
2.
- If n = 4q + 4, number of positive odd numbers less than or
equal to n is, ⌈(4q + 4)/2⌉ = 2q + 2.

We can see
that the number of odd numbers less than or equal to n is even if and
only if n ≡ 3 (mod 4) or
n ≡ 0 (mod 4).

**… (2)**
From (1) and (2), the necessity of the condition n ≡ 3 (mod 4) or
n ≡ 0 (mod 4) is proven.

### Proof of the sufficiency of the condition n ≡ 3 (mod 4) or n
≡ 0 (mod 4):

If we can show that we can construct a permutation that satisfies the
condition in the question for every positive integer n such that n
≡ 3 (mod 4) or n ≡ 0 (mod 4), then the proof would be
complete. We have two cases to deal with:

- n ≡ 3 (mod 4)
- n ≡ 0 (mod 4)

When, n ≡ 3 (mod 4), let
x = (n + 1) / 4. Partition the first n
natural numbers in 4 sequences, p_{1}, p_{2},
p_{3} and p_{4} such that each sequence contains
x − 1 numbers and 3 single numbers a, b and c according
to the following rules. This is possible since, 4(x − 1)
+ 3 = 4x − 1 = n + 1 − 1 = n. The
partitioning rules are as follows.

- a = 2x − 1
- b = 4x − 2
- c = 4x − 1
- p
_{1} = Odd numbers
between 1 and a in ascending order. (1, …,
2x − 3).
- p
_{2} = Even numbers between 1 and a in ascending order. (2,
…, 2x − 2).
- p
_{3} = Odd numbers between a and b in ascending order.
(2x + 1, …, 4x − 3).
- p
_{4} = Even numbers between a and b in ascending order.
(2x, …, 4x − 4).

It can be verified that the above
partitioning rules imply that the length of each partition p_{i}
is x − 1 where 1 ≤ i ≤ 4. Also, all natural
numbers less than or equal to n are present in the 4 partitions and 3
single numbers above.

Let us consider an array A of size 2n. The first index of array is 1.
Now, a valid permutation can be formed with the following placement
rules.

- A[1] to A[x − 1] contains reversed
p
_{4}.
- A[x] to A[2x − 2] contains reversed
p
_{1}.
- A[2x − 1] contains b.
- A[2x] to A[3x − 2] contains p
_{1}.
- A[3x − 1] contains c.
- A[3x] to A[4x − 2] contains p
_{4}.
- A[4x − 1] contains a.
- A[4x] to A[5x − 2] contains reversed
p
_{3}.
- A[5x − 1] to A[6x − 3] contains
reversed p
_{2}.
- A[6x − 2] contains b.
- A[6x − 1] contains a.
- A[6x] to A[7x − 2] contains p
_{2}.
- A[7x − 1] contains c.
- A[7x] to A[8x − 2] contains p
_{3}.

Note that 8x − 2 = 2n. So, the
last rule can be rewritten as "A[7x] to A[2n] contains p_{3}".

When n ≡ 0 (mod 4), let x = n / 4.
Partition the first natural numbers in 4 sequences, p_{1},
p_{2}, p_{3} and p_{4} such that each sequence
contains x − 1 numbers and 4 single numbers a, b, c and
d. The partition rules contain the 7 rules discussed above and one more
rule. The additional rule is: d = 4x.

The placement are same for all cells in the array with one exception and
two additional rules for the two new cells.

- A[4x − 1] = d. (Exception. Modifies rule 7.)
- A[8x − 1] = a.
- A[8x] = d.

With these rules it can be shown that two k's have k elements in
between. In other words, the difference in the array indices of the
cells where two k's are present is k + 1.

a = 2x − 1. The two a's are located at
A[4x − 1] and A[6x − 1]. The difference
in array indices is 2x. Hence, two a's have 2x − 1 = a
numbers in between. Similarly, this can be verified for b, c and d.

The two 1's are located at A[2x − 2] and A[2x]. The
difference in array indices is 2. Hence, the two 1's have 1 number in
between. From this it can be shown that for each k in p_{1},
there are k numbers in between. Take an arbitrary element m in
p_{1}. From the construction rules, we see that, the two m's are
located in
A[2x − 2 − (m − 1)/2]
and A[2x + (m − 1)/2]. The difference in the indices is:
2x + (m − 1)/2 − 2x + 2 +
(m − 1)/2 = m + 1. Similarly, it can be shown that for
any k in any parition p_{i} (1 ≤ i ≤ 4), there are k
numbers between the two k's.

Here is an example.

n = 11
x = (11 + 1) / 4 = 3
a = 5
b = 10
c = 11
p1 = (1, 3)
p2 = (2, 4)
p3 = (7, 9)
p4 = (6, 8)
(a)
+------------+
(c) | |
+-----|------------|------+
(b) | | | |
+------|-----|----------+ | |
| | | | | |
8 6 3 1 10 1 3 11 6 8 5 9 7 4 2 10 5 2 4 11 7 9
=== === === === === === === ===
| | | | | | | |
| +------+ (p1) | | +--------+ (p2) |
+-----------------+ +-------------------+
(p4) (p3)

### Notes

- There is an entry for this problem in OEIS: http://oeis.org/A014552.
- The internal symmetries in the permutation are not very obvious from
the proof but the permutation simply requires us to place a, b, c,
p
_{1}, p_{2} and p_{3} in this order:
(p_{4}' p_{1}' b p_{1} c p_{4} a
p_{3}' p_{2}' b a p_{2} c p_{3}) when n
≡ 3 (mod 4), where p_{i}' is reversed p_{i} (1
≤ i ≤ 4).
- For n = 3, we get x = 1. So, length of the partitions p
_{1},
p_{2}, p_{3} and p_{4} is x − 1
= 0 each. So, rules that involve the partitions do not apply in case of
n = 3.
- In this proof, I have shown one set of rules to construct a valid
permutation for a given n such that n ≡ 3 (mod 4) or n ≡ 0
(mod 4). But actually, I found 2 such sets of rules. The variables a, b,
c and d remain same in the other rule. Only the rules for
p
_{1}, p_{2}, p_{3}, p_{4} and placement
rules differ.
- The above two points imply that, except for n = 3, using
construction rules, we can construct at least two different permutations
for a given value of n such that n ≡ 3 (mod 4) or n ≡ 0 (mod
4).
- It seemed like for values of n > 20, there might be over a
quadrillion possible solutions. It wasn't feasible to verify this on my
laptop with the program I wrote. When I discussed this with a person who
was interested in this problem, he asked, "What? Don't you have a
quad(rillion)-core processor?"
- I worked through a Saturday night till 3:30 AM of the following
Sunday morning and I could prove only the necessity of the condition n
≡ 3 (mod 4) or n ≡ 0 (mod 4). When a friend asked me about the
progress, I could manage to say this, "Half of it. Need to prove a
'necessary and sufficient' condition. Proved the necessary part only but
this much is sufficient for me today. The sufficient part is necessary
for the proof to be complete but i think, now it has become necessary to
do the sufficient part tomorrow as it is too late already."
- The above point reminds me of a famous quote by George Pólya,
"Mathematics consists in proving the most obvious thing in the least
obvious way".
- The above point reminds me of http://humor.beecy.net/misc/principia/.