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 displacement of $(13, 13)$. This could be achieved either by placing two new counters next to the unused corners, or by placing one new counter in the free space diagonally adjacent to the counter in the bottom right. The first of these possibilities can be ruled out since the two new counters would both be the same distance from the existing counters in the corners.
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!
You cannot get n for any large enough n: https://math.stackexchange.com/a/1216013/88597
I eventually wrote a program using a SAT solver (via the PySAT library) to encode the constraints and the information that there have to be at least $n(n-1)/2$ distinct distances. It solves all the cases from $n = 0$ to $15$ in less than two minutes total! Code: https://oscarcunningham.com/public_share/unique-distances.py
I think there’s a case not treated: when you do the third largest distance, that could instead be a cell horizontally adjacent to a corner and another vertically adjacent to the opposite corner.
There are other possibilities for that on the grid, using the unused corners.
Hi James, good point! In fact that case is immediately ruled out because the two new counters would both be the same distance from the counters in the corners. I don’t know how I missed that the first time, I’ll add it in now.