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. Continue reading →