Interview question - numbered tiles 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?

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$).
