6
$\begingroup$

A set of line segments inside or at the edge of a square with side length 1 should be positioned in such a way, that any straight line going through the square must touch or intersect at least one of the line segment. Find such a configuration where the total length of all such line segments is minimal?

Example: choose the 4 sides of the square as line segments. The length of those line segments is 4. A better choice are the two diagonals of the square with a total length of $2\times\sqrt2$ ~ 2,828. Can you improve further?

$\endgroup$
5
  • $\begingroup$ Technically we can calculus the line segments into curves if we so please. $\endgroup$ Commented Sep 20, 2019 at 20:26
  • $\begingroup$ well, the line segments should be straight lines, if you want to clarify that. $\endgroup$
    – ThomasL
    Commented Sep 20, 2019 at 20:33
  • $\begingroup$ @greenturtle3141 While true, I can't think of any situations in this puzzle where we would prefer curves to straight lines. $\endgroup$
    – Surma
    Commented Sep 20, 2019 at 20:39
  • $\begingroup$ Two related puzzles: Find a straight tunnel and Find a straight tunnel 2 $\endgroup$ Commented Sep 20, 2019 at 20:51
  • $\begingroup$ Very nice one! Deceptively appears to be rather easy to solve ... $\endgroup$
    – collapsar
    Commented Sep 21, 2019 at 13:41

3 Answers 3

8
$\begingroup$

Building on LOTGP's answer, you could do this:

enter image description here

Assuming a unit square, the total length is:

The top left segment is $\sqrt{2}/2$. The three other segments are shortest when they meet at 120 degrees. This makes the triangle angles $(120, 45, 15)$. Using the sine rule, that gives
$\sin{45}/\sin{120} \approx 0.8164$ for the long sides
$\sin{15}/\sin{120} \approx 0.2988$ for the short sides
for a total of about $2.638958$.
This is a slight improvement over LOTGP's answer which is $2+\sqrt{2}/2 \approx 2.707107$.

$\endgroup$
2
  • 2
    $\begingroup$ According to wikipedia, this is the best known answer. However, our site policy dictates that you must invent some new mathematics and prove the optimality, or your brilliant solution does not count as an answer at all, and should be posted as a comment or community wiki instead. (If this policy seems unfair, there's a recent meta post to that effect currently active.) $\endgroup$
    – Bass
    Commented Sep 21, 2019 at 8:16
  • $\begingroup$ Well done! If you use roots for the trigonometic values, you can write it as $$\sqrt{2}+\sqrt{1.5}$$ $\endgroup$
    – ThomasL
    Commented Sep 21, 2019 at 14:02
8
$\begingroup$

Seems a slightly better solution would be to:

cover 2 of the sides that meet at one of the corners, then draw the half diagonal from the opposite corner to the middle.

Something like this:

Picture

The total length is then:

1 + 1 + sqrt(2)/2 = 2.707

$\endgroup$
1
  • $\begingroup$ good finding! But I know that there is at least one more improvement... $\endgroup$
    – ThomasL
    Commented Sep 20, 2019 at 20:20
2
$\begingroup$

Observation 1 (trivial):

There must be a segment touching each corner of the square

Observation 2 (non-rigorous):

Consider the solution of both main diagonals. Any other solution consisting of exactly 4 segments with a single intersection point has a greater length than the both diagonals.
> This can be seen by moving the intersection point and repeatedly replacing any segment by a polyline of 2 segments. Due to the triangle inequality any of these operations increases the length of the segment set. Note that (well-behaved) curves can be approximated to an arbitrary precision by polylines so this construction is not limited to sets of straight segments (some technicalities are missing for a mathematically rigorous proof).

Working assumption:

The solution will be a connected structure. The structure shall thus map to a connected graph of minimal geometrical edge length that links all 4 corners of the unit square.

There is a structure that precisely realizes these needs:

A Steiner tree, which can be seen here: Steiner tree in unit square The total length of segments is approx. 2.732

What is missing for optimality ( or: the dangers of intuition) ?

The proof that the minimal structure must be connected. It seems intuitively obvious that if the structure is disconnected, either a corridor can be found through which rays can pass that intersect two sides of the square or the structure is way too long. This needs to be formalized however to be sure.

Update

After peeking into the other solutions, i found my intuition proved wrong ... The structure need not be connected. However, among the connected ones, the Steiner tree is optimal.

$\endgroup$

Your Answer

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

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