The Dot Game

A work in Progress!

The antidote to boredom is curiosity

I often find that the mundane and seemingly simple things can, when explored, lead to rather unexpected outcomes. This is a tale of my journey into the world of dots, and it all started, as many things do, as an antidote to boredom: curiosity.

A riveting math class had led me to staring at my notepad, doodling in between the dots, when I pondered the question:

How many dots can you have on a unit grid so that the gradient between any two dots is unique?

Repeated gradients: invalid

Valid solution to a 5 grid

It soon became clear that the theoretical maximum number of dots you can place on a dot grid of size N is, for all grids, N + 1, as once there are two dots in any row and column, there can be no more.

Now it was onto the task of finding the solutions with the theoretical maximum number of dots. 2 and 3 were simple, but 4 took a good while longer. 5 took over 20 minutes, but 6 was seemingly impossible.

Please, try to solve the puzzle yourself ( There are multiple solutions.)

Method

Initially, a random search was used to find solutions. We select random coordinates, and if any gradients are shared, a new point is chosen, until a solution is found or we terminate and start again after x number of tries.

This method was used to find solutions up to the 6 by 6 grid, but only 7 dots could be placed on the 7 by 7. The number of dots placed in higher-order grids is shown in Figure 1.

Clearly, proof was required to confirm if the limit for the 7 by 7 could not be reached, so an exhaustive method of search was coded. As grid sizes increase, the search time increases exponentially.

Figure 1: number of solutions for higher order grids

Unique Solutions

Now, with exhaustive search, I had all the possible solutions to the dot grid. But how many unique solutions are there? For the case of 2D, 6 matrices can be used to compare all solutions. The number of unique solutions ( after rotation, reflection, inversion, etc ) is shown in Figure 2. To extend this to 3D, 48 matrices are required.

Figure 2: number of unique solutions.

The 3 unique solutions for placing 7 dots on a 6 by 6:

Theory

Although the solutions were found, the reason behind was still a mystery. To approach the problem from a more mathematical background, the number of gradients was investigated. This was completed using exhaustive methods in Python.

Figure 3 highlights the complexity of the problem. The Spikes are present due to a large increase in new gradients when a prime number grid is used. Due to the somewhat random nature of prime numbers, it became clear that I do not possess the mathematical tools to solve this theoretically.

Figure 3: New gradients generated as grid size increases

It was believed that the possible number of dots able to be placed could be limited by the available gradients, but no such limiting factor could be found.

The move to 3D

Figure 5: The only solution for 8 dots on a 3 grid in 3D.

The trivial limit for 2D of N + 1 dots on an N-sized grid cannot, as far as I am aware, be extended to the case of higher dimensions. After looking at the literature, only estimates have been found. This complicates the search as we do not know what the theoretical maximum could be. Additionally, the computation time for exhaustive search gains an additional factor of N^(3/2). We compare aligned vectors instead of gradients for 3D.

Furthermore, visualisation becomes a lot more challenging and finding solutions without the aid of computers becomes, at least for me, virtually impossible.

Relation to Condensed Matter Physics

Figure 6: The 14 Bravais lattices in 3D, showing symmetry to the 14 unique solutions for a 4 grid in 2D.

There is a notable comparison between the number of unique solutions for a 2, 3, and 4 grid in 2D: 1, 5, and 14, respectively. This is the number of Bravais lattices in 1D, 2D and 3D in the field of condensed matter physics. This is most probably a coincidence, as unfortunately, this breaks for 4D. But considering the crystal nature of lattices and the symmetry rules governing crystal systems, it does lead one to ponder and

An Ode to Beautiful Uselessness

It has been many years since I began this project, and I have learned more than I could ever have initially imagined. What was a test of my logical thought tested me in what I wish to do with this life, and bigger questions such as why we do anything.

I posed my project to my academic supervisor, summarising what is outlined above. I got the following response.

' I would be happy to work with you, but I can't work on things that are solely beautiful... I only address them during my holidays when I feel I can be extravagant. My physics has to be useful and beautiful.'

I know somewhere in this world, this problem has been solved, for someone it was a Tuesday afternoon's work. Why should I spend my time searching for the path that has probably been walked before? As time ticks on, how many paths are undiscovered, and what is the use in following?

This project has taught me to do what I love and find passion for what brings me curiosity, even if the same curiosity has struck many before.

Page updated

Google Sites

Report abuse