1
$\begingroup$

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:

enter image description here

enter image description here

Example 2:

enter image description here

enter image description here

  • Add any tags that you think are relevant.
  • Should the graph-theory tag be added?
Improve this question
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Dennis Meng
    May 28, 2015 at 5:24
  • $\begingroup$ @DennisMeng Yes that is correct. Good point. $\endgroup$
    – JLee
    May 28, 2015 at 5:38
  • $\begingroup$ Downvoter(s): Care to comment? Is this puzzle too easy? Or is it something else? $\endgroup$
    – JLee
    May 28, 2015 at 14:11

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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! $\endgroup$
    – JLee
    May 28, 2015 at 5:36
  • $\begingroup$ 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. $\endgroup$
    – JLee
    May 30, 2015 at 23:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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