Jump to content
BrainDen.com - Brain Teasers
  • 0
bonanova

Shortest roads

Question

Four towns, A, B, C and D, are located such that their centers form the vertices of a square 1 mile on a side. Town planners want to build a set of roads that connect the four town centers while minimizing the cost, which can be considered to increase linearly with road length.

What set of roads minimizes that cost?

A               B
 

C               D

Share this post


Link to post
Share on other sites

6 answers to this question

  • 0
11 minutes ago, Thalia said:

 

  Hide contents

Make an X? Length would be 2*sqrt2 mi. Seems too easy though...

 

You're correct. It can be a little bit shorter than that.

Share this post


Link to post
Share on other sites
  • 1

How about

Spoiler

Total length: (2*sqrt(5) + 1) / = 2.7361

It would look something like this:

\__/
/  \

 

 

Share this post


Link to post
Share on other sites
  • 1

I think...

Spoiler

Let a diagonal road connect each of the four towns to the endpoints of a vertical road that runs through the center of the square. Call the length of the vertical road x. Then the total length of all of the roads, geometrically, is

 

T = x + 2√(x2 -2x +2)

 

Then, dT/dx = 1 + (2x -2) / √(x2 -2x +2), which has a zero at x = 1 - (1/√3). The total road length, by the above formula, is then ~2.73205.

Special thanks to Cygnet for suggesting there might be a minimum hidden in such a configuration. ^_^

Share this post


Link to post
Share on other sites
  • 0
8 hours ago, ThunderCloud said:

I think...

  Hide contents

Let a diagonal road connect each of the four towns to the endpoints of a vertical road that runs through the center of the square. Call the length of the vertical road x. Then the total length of all of the roads, geometrically, is

 

T = x + 2√(x2 -2x +2)

 

Then, dT/dx = 1 + (2x -2) / √(x2 -2x +2), which has a zero at x = 1 - (1/√3). The total road length, by the above formula, is then ~2.73205.

Special thanks to Cygnet for suggesting there might be a minimum hidden in such a configuration. ^_^

I assumed my answer was along the right lines, but I was too lazy to actually find the true minimum with it...thanks for doing the dirty work!

Share this post


Link to post
Share on other sites
  • 0

Another approach:

Spoiler

Let the small angle in the diagram be theta. Total length then is 1 + 2 sec(theta) - tan(theta), whose derivative is (2 sin(theta) - 1)/cos2(theta) which is zero for theta=30o. The three lines intersect, nicely enough, at 120o. Using 30o for theta, the length is 1 + (4-1)/sqrt(3) = 1 + sqrt(3), which is ThunderCloud's result

 

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.

×