- 16 May '08 23:02Suppose 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. - 17 May '08 06:22

3. A road from A to B, one from B to C, one from C to D.*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. - 17 May '08 07:23

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.*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}.

So, for the record: 2*sqrt(2) is not the optimal solution. - 17 May '08 09:34 / 3 editsI 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. - 17 May '08 09:44if 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 - 17 May '08 09:58

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 - 17 May '08 10:03

Damn.*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 have 2.736....

1/2 + sqrt(5) - 17 May '08 16:33

Somehow I decided 2{2} was more than 3. Oh well =/*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}. - 17 May '08 17:34A 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√(x2 + ½2) = 1 - 2x + 4√(x2 + ¼

Differentiating: dL/dx = -2 + 4x/√(x2 + ¼

Let this equal 0, finding the minimum point of the first expression:

4x/√(x2 + ¼ = 2

2√(x2 + ¼ = 4x

√(x2 + ¼ = 2x

square:

x2 + ¼ = 4x2

¼ = 3x2

x = √(1/12) = ½ √(1/3)

Which agrees with Dejection, as tan-1(1/√3) is 60" - 17 May '08 17:56

That is correct.*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.

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