14
$\begingroup$

Can you paint $7$ cells of a $7 \times 7$ grid such that the Euclidean distance* between any pair of painted cells is distinct? Good luck!

*The Euclidean distance between cells $(r_1,c_1)$ and $(r_2,c_2)$ is $\sqrt{(r_1-r_2)^2+(c_1-c_2)^2}$.

$\endgroup$
3
  • 1
    $\begingroup$ Note I am calling it Golomb square even though such a name doesn't exist. It is related to Golomb rulers and Costas arrays, but different to them. $\endgroup$ Apr 22 at 12:57
  • $\begingroup$ There is a nice integer sequence for this problem: oeis.org/A193838 $\endgroup$ Apr 23 at 11:52
  • $\begingroup$ In the sequence above I've added solutions for larger grids. $\endgroup$ Apr 28 at 0:58
11
$\begingroup$

I don't know how you would be able to deduce a solution to this, so I used a computer. It turns out that the solution is unique (ignoring rotation and reflection).

 X . . X . . .
 . . . . . . .
 X X . . . . .
 . . . . . . .
 . . . . . . .
 . . . . . X .
 . . X . . . X

My C# program does a straightforward exhaustive search:

  using System;
  using System.Collections.Generic;

  namespace TempProg
  {
     class PSEGolombSquare
     {
        private const int N = 7; // grid size
        private const int S = 7; // number of squares

        public static void Main()
        {
           DoSearch(new int[S], 0);
        }

        private static void DoSearch(int[] coords, int nextIndex)
        {
           if (nextIndex == coords.Length)
           {
              // founf a solution
              foreach (int i in coords)
                 Console.Write("{0}{1}  ", i % N, i / N);
              Console.WriteLine();
              return;
           }
           // add another square
           int first = nextIndex == 0 ? 0 : coords[nextIndex - 1] + 1;
           for (int c = first; c < N * N; c++)
           {
              coords[nextIndex] = c;
              if (IsValid(coords, nextIndex + 1))
                 DoSearch(coords, nextIndex + 1);
           }
        }

        private static bool IsValid(int[] coords, int num)
        {
           ISet<int> distances = new SortedSet<int>();
           for (int i = 0; i < num; i++)
           {
              for (int j = i+1; j < num; j++)
              {
                 int d = GetDistance(coords[i], coords[j]);
                 if (distances.Contains(d)) return false;
                 distances.Add(d);
              }
           }
           return true;
        }

        private static int GetDistance(int v1, int v2)
        {
           int dx = v1 % N - v2 % N;
           int dy = v1 / N - v2 / N;
           return dx * dx + dy * dy;
        }
     }
  }
$\endgroup$
3
  • 1
    $\begingroup$ Correct. That's the solution I have. I was surprised that it is unique only for this particular grid size. Let's see if anyone can find this by hand. $\endgroup$ Apr 22 at 12:59
  • 2
    $\begingroup$ Confirmed 8 isomorphic solutions via integer linear programming. $\endgroup$
    – RobPratt
    Apr 22 at 13:33
  • 2
    $\begingroup$ Almost posted my by hand (other) solution; forgot about the 3-4-5 triangle :-( $\endgroup$
    – Retudin
    Apr 22 at 13:57
2
$\begingroup$

Matt Parker hosted a challenge to solve this puzzle last year. The participants found that there were two distinct solutions for 6x6, one for 7x7, and none for 8x8 or 9x9 (up to rotations/reflections).

https://youtu.be/G0i_YSFvMb0?t=366

According to comments on the video, the search was extended with no solutions found up to 14x14, and you can prove that no solutions exist for larger grids because there are more combinations of pairs of points than there are possible distinct distances.

https://oscarcunningham.com/670/unique-distancing-problem/

$\endgroup$
14
  • 1
    $\begingroup$ Could you please provide copies of the proofs/solutions within your answer? This makes it self-contained, so people don't have to watch an external video/read an external link to find the answer. It also protects against link rot. $\endgroup$
    – bobble
    Apr 22 at 22:02
  • $\begingroup$ @bobble The solution for 7x7 is identical to the one in the accepted answer, and does not need to be repeated. The proof for large n is already included, it is the one line statement "there are more combinations of pairs of points than there are possible distinct distances". $\endgroup$
    – Brady Gilg
    Apr 22 at 22:41
  • $\begingroup$ That one line seems to me like it needs some further elaboration. The easy bound is # possible distances <= about 3/4 (n-1)^2 which isn't smaller than n(n-1)/2. In the limit of large n, a famous theorem of Landau shows that there aren't enough distinct distances, but (1) it's quite nontrivial and (2) I don't know whether it gives explicit bounds that would let you show that n >= 14 is enough. Am I missing something? $\endgroup$
    – Gareth McCaughan
    Apr 22 at 23:28
  • $\begingroup$ (sorry, should have put @BradyGilg in that) $\endgroup$
    – Gareth McCaughan
    Apr 22 at 23:29
  • $\begingroup$ (I had a look at the video, and it seems like no one actually proved you can't do it for n>14; they checked a bunch of specific cases and showed that the required inequality holds, and they quoted the Landau result which shows that for large enough n there are no solutions, but I don't see any sign of an actual proof that has the necessary quantitative estimates.) $\endgroup$
    – Gareth McCaughan
    Apr 22 at 23:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.