Shortest Road Length

Suppose we have four cities that lie at the vertices of a square with edge length of 1 (arbitrary unit). What is the minimum total length of road that would connect all the cities (such that one could drive from any one city to any of the remaining three cities)?

If you have already seen this question, maybe just PM me the solution so that others may have a chance to work on it.

Originally posted by LemonJello
Suppose we have four cities that lie at the vertices of a square with edge length of 1 (arbitrary unit). What is the minimum total length of road that would connect all the cities (such that one could drive from any one city to any of the remaining three cities)?

If you have already seen this question, maybe just PM me the solution so that others may have a chance to work on it.

3. A road from A to B, one from B to C, one from C to D.

Originally posted by AThousandYoung
3. A road from A to B, one from B to C, one from C to D.

I can beat 3.
😛

{x} = the square root of x

I haven't seen it before, but I got 2{2} = ~2.8 miles. But this seems like too easy/obvious an answer. I've tried imagining different minimizing techniques, but they all end up at 2{2}.

Originally posted by Jirakon
{x} = the square root of x

I haven't seen it before, but I got 2{2} = ~2.8 miles. But this seems like too easy/obvious an answer. I've tried imagining different minimizing techniques, but they all end up at 2{2}.

You're right that 2*sqrt(2) would be too easy, too obvious. The question is a bit more difficult than it might appear at first.

So, for the record: 2*sqrt(2) is not the optimal solution.

Can I just check - you're talking about a flat plane? No tricks with the geometry?

Originally posted by mtthw
Can I just check - you're talking about a flat plane? No tricks with the geometry?

That's correct, I am talking about a flat plane. There are no "tricks" here.

I have done better than 2{2}:
X is a city
O is a road

X......................X
...OOO........OOO
........OO.OO
............O
............O
............O
........OO.OO
...OOO.......OOO
X......................X

There are five different line segements there, and all angles are 120 degrees. The total length is 1+{3} < 2{2}. I can't do any better.

if you do a sort of v shape on both sides then a stick in the middle, you seem to get the shortest answer. When the length of that stick in the middle is 0, then the total length used is 2 root 2. When the length of that stick is 1, then the total length is 3.

To one decimal place, the length of the stick should be 0.4 which gives us a total length of 2.732...

When the stick is length x, the total length is x+4(((1-x)/2)^2+0.25)^0.5
DA/DX=1-2(((1-x)/2)^2+0.25)^-0.5(((1-x)/2)^2)

someone else feel free to expand that out and find the optimum value. I'm happy with a stick length of 0.4

Originally posted by doodinthemood
if you do a sort of v shape on both sides then a stick in the middle, you seem to get the shortest answer. When the length of that stick in the middle is 0, then the total length used is 2 root 2. When the length of that stick is 1, then the total length is 3.

To one decimal place, the length of the stick should be 0.4 which gives us a total length ...[text shortened]... e feel free to expand that out and find the optimum value. I'm happy with a stick length of 0.4

I get the two triangles of height ~.29 each, and the connecting road .42, but how can we be sure this is optimum?

Originally posted by doodinthemood
if you do a sort of v shape on both sides then a stick in the middle, you seem to get the shortest answer. When the length of that stick in the middle is 0, then the total length used is 2 root 2. When the length of that stick is 1, then the total length is 3.

To one decimal place, the length of the stick should be 0.4 which gives us a total length ...[text shortened]... e feel free to expand that out and find the optimum value. I'm happy with a stick length of 0.4

Damn.
I have 2.736....

1/2 + sqrt(5)

Originally posted by Jirakon
{x} = the square root of x

I haven't seen it before, but I got 2{2} = ~2.8 miles. But this seems like too easy/obvious an answer. I've tried imagining different minimizing techniques, but they all end up at 2{2}.

Somehow I decided 2{2} was more than 3. Oh well =/

A kid from my school suggested this:

"Let the length of stick be 1-2x (and the depth of the “V” be x). Then total length is 1 – 2x + 4&#8730;(x2 + ½2) = 1 - 2x + 4&#8730;(x2 + ¼😉

Differentiating: dL/dx = -2 + 4x/&#8730;(x2 + ¼😉

Let this equal 0, finding the minimum point of the first expression:
4x/&#8730;(x2 + ¼😉 = 2
2&#8730;(x2 + ¼😉 = 4x
&#8730;(x2 + ¼😉 = 2x
square:
x2 + ¼ = 4x2
¼ = 3x2
x = &#8730;(1/12) = ½ &#8730;(1/3)

Which agrees with Dejection, as tan-1(1/&#8730;3) is 60"

Originally posted by Dejection
I have done better than 2{2}:
X is a city
O is a road

X......................X
...OOO........OOO
........OO.OO
............O
............O
............O
........OO.OO
...OOO.......OOO
X......................X

There are five different line segements there, and all angles are 120 degrees. The total length is 1+{3} < 2{2}. I can't do any better.

That is correct.

This is an example of a Steiner tree problem, and the 120 degree stipulation is the key idea for such problems.

Originally posted by LemonJello
That is correct.

This is an example of a Steiner tree problem, and the 120 degree stipulation is the key idea for such problems.

Very interesting. Never come across that before.