# Find the optimal dot configuration

## Rules:

1. You have 9 dots, labeled A through I.
2. You choose a layout (arrangement) for the 9 dots.
3. You must connect the 9 dots with straight lines (no curves or extra lines).
4. The object is to minimize the "Connect Factor."
5. The closest that any 2 dots can be to each other is 1 unit.

## Disclaimer:

There is most likely only one optimal solution, but I do not know what it is (yet).

## Info:

• There are 36 distinct paths (9 choose 2). Namely, AB, AC, AD, ... , GH, GI, HI
• Consider 2-dimensional and 3-dimensional. Get creative. I have a feeling that the optimal answer is a 3-d layout (maybe 8 points evenly distributed around a dot, 1 unit from it, if that is possible? or some variation of that?)
• Eventually I would like to extend this to other numbers of dots, but for now, let's optimize 9.

## Connect Factor Formula:

A = The average of the 36 path lengths
N = Total number of lines used

Connect Factor = A + N

## Example 1:  # Example 2:  • Add any tags that you think are relevant.
• Should the graph-theory tag be added?
• Just so it's spelled out (I already got tripped up by this), when we say path length between two points, we mean to take the sum of the lengths of the segments in the (shortest) path between the two, right? May 28, 2015 at 5:24
• @DennisMeng Yes that is correct. Good point.
– JLee
May 28, 2015 at 5:38
• Downvoter(s): Care to comment? Is this puzzle too easy? Or is it something else?
– JLee
May 28, 2015 at 14:11

In 3 dimensions, position three on an axis in a row, each one unit apart. On the center one, construct a hexagon of the other 6 points on the perpendicular plane. These 6 points are now 1 unit from each other and 1 unit from the center.

Draw lines connecting only to the center.

Distance from outer point to center point: 1 (8 times) Distance from outer point to outer point: 2 (28 times)

Average: $\frac{8+2\times28}{36} = 1\frac{7}{9}$
Number of lines: 8

Connect factor: $9\frac{7}{9}$

Is it optimal? I think it might be. Why?
With 9 points, we must draw at least 8 lines in order to make a connected graph. An optimal solution must use 8. Suppose the optimal solution used 9. It would need to calculate a connect factor smaller than above, leaving only $\frac{7}{9}$ for the average path length. However, each path must be at least length 1. Therefore, an 8 line solution is optimal.

Could there be an 8-line solution that has an average length shorter than $1\frac{7}{9}$? No. If this were the case, then one of the paths that I previously indicated as "outer" would need to be of length less than 2. In order to be less than 2, its connection must not go through the common point and be a direct connection. However, this means that other points would connect to it through this other outer point, increasing all of their path lengths by 1 and inflating the average.

There's a lot of vertex counting that could be done here to formally prove all of this, but I'll leave that as an exercise to the reader.

• I thought on this for 5 days and never considered this, and then, 30 minutes after posting the question, as I was falling asleep, I thought of this exact setup, and signed back on to post the idea as a comment, and you beat me to it!
– JLee
May 28, 2015 at 5:36
• I wish I would have asked this same question, but with 19 points instead. I think the solution is much more interesting. Nevertheless, good answer.
– JLee
May 30, 2015 at 23:31