Is it possible to arrange the integers $1, 1, 2, 2,..., 1998, 1998$ such that there are exactly $i − 1$ other numbers between any two $i$'s?

Question

Is it possible to arrange the integers $1, 1, 2, 2,..., 1998, 1998$ such that there are exactly $i − 1$ other numbers between any two $i$'s?

This is a problem related to invariants and I'm trying to make sense of it by replacing $n= 1998$ with smaller values of $n$, but I cant't figure out how to define a suitable invariant here.

If we pick $n = 4$ we are looking at the sequence $$1,1,2,2,3,3,4,4$$ and the closest I can get to a working configuration is first fixing the $4$'s and then trying to organize the remaining numbers such that they satisfy the property. What I have is $$4,3,1,2,1,4,2,3$$ which works for all $i$ except $i=3$.

Now there should be something obstructing me from being able to get the desired configuration which would lead me to find the invariant, but I'm not seeing what is my obstacle here. Any hints on what to look for?

Edit: I made a mistake there shouldn't be any number between $1$'s. Actually for $n=4$ the configuration $$1,1,4,2,3,2,4,3$$ works.

Answer 1

Expanding your attempt

When $n=1$, there is sequence $1,1$.
When $n=2$, it is impossible.
When $n=3$, it is impossible.
When $n=4$, there is $1, 1, 3, 4, 2, 3, 2, 4$. Or $1,1,4,2,3,2,4,3$ as you have found.
When $n=5$, there is $1, 1, 3, 4, 5, 3, 2, 4, 2, 5$.
When $n=6$, hmm, it looks impossible.
When $n=7$, hmm, it looks impossible.
When $n=8$, there is $1, 1, 2, 5, 2, 6, 7, 8, 5, 3, 4, 6, 3, 7, 4, 8$.
When $n=9$, there is $1, 1, 2, 4, 2, 7, 8, 4, 9, 6, 3, 5, 7, 3, 8, 6, 5, 9$.

It looks when $n=0,1\pmod4$, there is such a sequence. Otherwise, there is no such sequence.

We would guess there is no such sequence when $n=1998=2\pmod4$. A proof is given below.

Parity argument

As you might have suspected, the invariant/classification is on parity.

Suppose we have arranged the integers $1,1,2,2,...,1998,1998$ in a row of $1998 * 2= 3996$ slots. Let us color the slots black and white alternatively as black, white, black, white, … Note that there are as many black spots as white spots.

• For each odd integer $i$, the two $i$'s should be arranged in two slots of different colors.
  So all odd integers occupy as many black spots as white spots.
  There are $3996-997*2=1998$ slots not occupied by the odd integers.
  Half of them, $997$ spots are black.
• For each even integer $i$, the two $i$'s should be arranged in $2$ slots of the same color.
  Since $997$ is not a multiple of $2$, all even integers cannot fill the $997$ black spots left.

Exercises:

1. Write another proof as suggested in Rezha Adrian Tanuharja's comment.

2. Prove the there is no such sequence when $n=1999$.

3. Construct such a sequence when $n=2000$.

4. Construct such a sequence when $n=2001$.

5. What happens if we should arrange the integers $1,1,2,2,...,n,n$ such that there are exactly $i$ other numbers between any two $i$'s?