1. Joined
    24 Apr '05
    Moves
    3061
    16 May '08 23:02
    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.
  2. SubscriberAThousandYoung
    All My Soldiers...
    tinyurl.com/y9ls7wbl
    Joined
    23 Aug '04
    Moves
    24791
    17 May '08 06:22
    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.
  3. Standard memberwolfgang59
    howling mad
    In the den
    Joined
    09 Jun '07
    Moves
    45641
    17 May '08 07:08
    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.
    😛
  4. In Christ
    Joined
    30 Apr '07
    Moves
    172
    17 May '08 07:14
    {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}.
  5. Joined
    24 Apr '05
    Moves
    3061
    17 May '08 07:23
    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.
  6. Joined
    07 Sep '05
    Moves
    35068
    17 May '08 08:07
    Can I just check - you're talking about a flat plane? No tricks with the geometry?
  7. Joined
    24 Apr '05
    Moves
    3061
    17 May '08 08:21
    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.
  8. Joined
    12 Sep '07
    Moves
    2668
    17 May '08 09:343 edits
    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.
  9. Joined
    31 May '07
    Moves
    696
    17 May '08 09:44
    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
  10. Joined
    14 Dec '05
    Moves
    5692
    17 May '08 09:58
    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?
  11. Standard memberwolfgang59
    howling mad
    In the den
    Joined
    09 Jun '07
    Moves
    45641
    17 May '08 10:03
    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)
  12. SubscriberAThousandYoung
    All My Soldiers...
    tinyurl.com/y9ls7wbl
    Joined
    23 Aug '04
    Moves
    24791
    17 May '08 16:33
    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 =/
  13. Joined
    31 May '07
    Moves
    696
    17 May '08 17:34
    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"
  14. Joined
    24 Apr '05
    Moves
    3061
    17 May '08 17:56
    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.
  15. Joined
    14 Dec '05
    Moves
    5692
    18 May '08 00:47
    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.
Back to Top