Unique Distancing Problem

The most recent of Matt Parker’s Maths Puzzles was the unique distancing problem:

For which $n\in\mathbb N$ is it possible to place $n$ counters on an $n\times n$ square grid so that there’s a different distance between each pair of distinct counters? (Distances are measured in the normal Pythagorean way, so if there is a counter at $(0,0)$ we cannot have counters at both $(5,0)$ and $(4,3)$).

For small $n$ the problem is not too hard. I managed to use a computer search to find solutions for $n<8$ and prove that there were no solutions for $8\leq n < 11$. For $n\geq 16$ it’s trivial that there are no solutions because the number of pairs of counters is greater than the number of distances possible on the grid. This leaves the cases $n = 11$, $12$, $13$, $14$ and $15$.

Fellow puzzler Gal Holowitz wrote code efficient enough to deal with four of these remaining cases, $n = 11$, $12$, $13$ and $14$, finding that there were no solutions for any of them. But for the $n=15$ case their code is still running!

So you would think that $n=15$ was the hardest case of all. But in fact you can prove that there are no solutions for this case by using just pen and paper. Here’s how.

On a $15\times 15$ grid there are $105$ possible distances, and the number of different pairs of counters is $15\times 14/2 = 105$. So each distance has to occur exactly once.

The largest distance possible is $\sqrt{14^2+14^2}=\sqrt{392}$, which is only achievable by counters in opposite corners of the grid. Let’s suppose the upper left and lower right.

Whenever we add any counters we can immediately rule out any positions which are equidistant from the placed counters, or whose distance from a placed counter is equal to the distance between two counters that have already been placed.

The next largest possible distance is $\sqrt{365}$, which can only be achieved by a counter in a corner and a counter in a square adjacent to the opposite corner. Since the other two corners have already been ruled out, we must have a counter next to one of our existing counters.

The second-to-next largest possible distance is $\sqrt{338}$, which can only be achieved by a counter in a corner and a counter diagonally adjacent to the opposite corner. There is only one possibility for that here.

The largest remaining possible distance is $\sqrt{340}$, which can only be achieved by a displacement of $(12,14)$. Again there is only one possibility.

Then the largest remaining distance is $\sqrt{317}$, which can only be achieved by a displacement of $(11,14)$. But there are no pairs of cells remaining that have this displacement!