Interview question - numbered tiles

Question

Ok, this interview question interested me and I would love to see an explanation!

There are some tiles: 1, 1, 2, 2, 3, 3

They must be placed in a straight line, such that there is one tile between the 1s, two tiles between the 2s and three tiles between the 3s.

E.g. 312132

Now, you could add two 4s: 41312432

But it is impossible to add two 5s.

The question is how to prove this..

What would be the proof, and how would you derive it?

Answer 1

Label the placement positions consecutively with the numbers $1, 2, ..., 10$.

Since the $1$-labeled tiles have to be placed one apart from each other, we can write their positions as $a$ and $a+2$ for some $1 \le a \le 8$.

Similarly, you can write the positions of the $2$-labeled tiles as $b$ and $b+3$ for some $1 \le b \le 7$.

Keeping up with the pattern, the $3$-labeled tiles are at $c$ and $c+4$, the $4$-labeled tiles are at $d$ and $d+5$, and the $5$-labeled tiles are at $e$ and $e+6$.

Now suppose you could successfully place all the pairs of tiles. This means that each of the placement positions $\{1, 2, ..., 10\}$ is covered by exactly one of the values $\{a, a+2, b, b+3, c, c+4, d, d+5, e, e+6\}$.

So that means that the sum of the values $\{1, 2, ..., 10\}$ is the same as the sum of the values $\{a, a+2, b, b+3, c, c+4, d, d+5, e, e+6\}$:

$$ \begin{align} \sum \{1, 2, ..., 10\} &= \sum \{a, a+2, b, b+3, c, c+4, d, d+5, e, e+6\} \\ 55 &= 2a + 2b + 2c + 2d + 2e + 20 \\ &= 2(a+b+c+d+e) + 20 \end{align} $$ which implies that $$ 2(a+b+c+d+e) = 35 $$ Since $a$, $b$, $c$, $d$, and $e$ are integers, that's not possible. So such a placement can't happen.

Answer 2

With tiles labeled $1,1,2,2,\ldots, n,n$ you have to place these at positions $1,2,\ldots, 2n$ such that the positions of the two tiles with label $k$ differ by $k+1$. Hence if $k$ is even, these tiles occupy one odd and one even position, whereas for odd $k$, the pair occupies two positions of equal parity. Hence if $r$ of the odd tile pairs occupy even positions and $\lfloor \frac{n+1}{2}\rfloor-r$ pairs occupy odd positions, we need that these counts are equal, i.e. $\lfloor \frac{n+1}{2}\rfloor=2r$. For $n=5$, the left hand side is odd, hence no such $r$ exists. (It may work again for $n=7$).