Project with tools for the 7th Matt Parker Math Puzzle problem.

• Solution for the problem stated in the MPMP7 youtube video.
• Solutions for smaller and larger grids.
• Solutions in 3 or more dimensional grids
• Can I fit more markers on the grid?
• Can I solve this on an 8x8 grid?
• Do solutions exist for larger 2D grids?

Yay, Matt mentiond my solution in MPMS: Unique Distancing Problem BTW, note the time offset 🤘

Arrange N counters on an NxN grid, such that all the distances between the counters are different.

The video

python3 mpmp7_unique_distances.py --width 6 --verbose

This will output these two solutions.

*.....
*.....
.....*
.*....
......
...*.*

or

*.....
......
*.....
...*..
....**
*.....

The script will not terminate immediately, since it will keep searching for more solutions, which it will not find.

I also wrote a C++ program to do the same, but much faster:

./mpmp7-unique-distances -p 6

First, as stated by Matt in his video, for the 3x3 case there are 5 solutions:

..*    ...    .**    ...    *.*
**.    ..*    ...    *.*    *..
...    **.    *..    *..    ...

Though you could argue that the first two, and also the last two look identical, with respect to translation. I did not look into counting those as duplicates.

Then the 2x2 grid, this one is pretty obvious, these are the two solutions:

*.   *.
*.   .*

The simplest grid, being the 1x1 grid has 1 solution:

*

Or is that the simplest? what about a 0x0 grid:

Well, I am not sure if that counts as 0 or 1 solution.

Here is a table listing the number of solutions for the remaining grid sizes:

Here is the solution for the 7x7 grid:

*..*...
.......
**.....
.......
.......
.....*.
..*...*

Now Why stop at flat grids, you can solve this for 3-D 'grids' as well:

Then in 4-D I was only able to solve this for 2x2x2x2 and 3x3x3x3 grids. The following table list the number of solutions found for the various higher dimensional grids:

in 5-D there are 5 solutions for the 2-sized grid. and more than 800 for the 3-sized grid, I did not wait for my program to complete it's search.

For the 3D and higher dimensional grids you can, here is a table of the most markers you can fit for a given size and dimension:

The empty slots in the table were computationally too expensive to determine.

Not with 8 markers, but there are 927 ways you can solve this with 7 markers.

Here is one solution:

*......*
*.......
........
*.......
.*......
.......*
..*.....
........

With less markers you can solve this ( obviously ). Here is a table listing the maximum number of markers you can fit on 2D grids:

Simple really: just pass the c++14 flag, there are no other dependencies.

clang++ -O3 -std=c++14 mpmp7-unique-distances.cpp -o mpmp7-unique-distances

• parameters 2 7 2 take really long --> most time spent rotating arrangements.
• most solutions are found in the first 10% of the running time --> maybe i am generating way too many arrangements, and i could stop searching way earlier.
• some, like 6 3 6, make a very wrong 'approxpersecond' estimate.
• Everything i wrote in the document might be wrong.

Willem Hengeveld [email protected]