Four towns, minimal roads

Geometry Level 5

Four towns (Abra, Bulbasaur, Charmander, and Dratini) happen to be located on the corners of a square with side length of 2 km as shown here as A, B, C, and D:

You, as an urban planner are in charge of planning a road that connects the four towns with the least possible road distance.

What is the least possible road distance (in kilometers) that you can use?

Give your answer to 2 decimal places.

The answer is 5.46.

1 solution

Geoff Pilling
Jan 2, 2017

The optimal solution is like this:

where all angles are $120^\circ$ .

For more on understanding why this would produce the minimum path here is a reference as this is an example of a Steiner tree. Thanks @Brian Charlesworth for pointing this out!

For this arrangement the four longer legs connecting to each city have a distance (in km) of:

$L_1 = \frac{2}{\sqrt3}$

And the length of the line segment in the middle is:

$L_2 = 2 - \frac{2}{\sqrt3}$

So, the total length of all roads will be:

$L_{total} = L_2 + 4L_1 = 2 + \frac{6}{\sqrt3} = \boxed{5.46}$ km when rounded to two decimal places.

Great problem! I started with diagonals and then realized I could make the road shorter using a "bridge" road in the middle. Apparently this is an example of a Steiner tree .

Potential follow-up question: Optimizing the length of an intergalactic highway joining 8 planets situated at the vertices of a cube with side length 1 parsec. :)

Brian Charlesworth - 4 years, 5 months ago

Ah... A 3D version! :)

Geoff Pilling - 4 years, 5 months ago

That would be pretty cool. But I have to be out of town, and I'm sure by the time I'm back, a bunch of people will have already solved it.

Michael Mendrin - 4 years, 5 months ago

...eh, I knew it. Geoff, ${L}_{2}=2-\frac {2}{ \sqrt{3} }$ . Fix your answer. It should have been $5.46$ , not $4.46$ .

Michael Mendrin - 4 years, 5 months ago

Oooops, you are right... Fixed!

Geoff Pilling - 4 years, 5 months ago

Thanks. Those who previously answered 5.46 has been marked correct.

Geoff, as a moderator, please do not edit options significantly, because that doesn't update it for other who already answered the problem. Instead, simply report the problem and staff will handle it delicately.

Michael, in future, if you spot any errors with a problem, you can “report” it by selecting "report problem" in the menu. This will notify the problem creator (and eventually staff) who can fix the issues.

Brilliant Mathematics Staff - 4 years, 5 months ago

@Brilliant Mathematics – OK, yeah, sounds good!

Geoff Pilling - 4 years, 5 months ago

The optimal solution is like this:

Why is it so?

Pi Han Goh - 4 years, 5 months ago

You might like to look at the solution to this problem .

Mark Hennings - 4 years, 5 months ago

Ah yes I know. If I'm not mistaken, Geoff didn't write the "it's because of Steiner" in his solution so I was under the impression that he got another way to obtain this optimal configuration.

I've already printed out your solution given in the link. Thank you very much!

Pi Han Goh - 4 years, 5 months ago

@Pi Han Goh – Pi is right. I added that to the solution after Pi asked the question... Hopefully it suffices to point people to the Steiner path web page rather than try to explain the theory in the solution...

Geoff Pilling - 4 years, 5 months ago

@Geoff Pilling – OK, but the Wikipedia link describes a Steiner point as one whose three edges subtend angles of $120^\circ$ with each other (all very true) without explaining why that it is desired configuration.

My solution does show how to calculate the minimum length (it is the distance $2 + 2\sqrt{3}$ between the vertices of equilateral triangles constructed on the bases $AC$ and $BD$ ), and why it is the minimum length.

Mark Hennings - 4 years, 5 months ago

@Mark Hennings – Good point, Mark... Do you mind if I provide a link to your solution in my problem, for those who want to understand the theory behind Steiner trees a bit better?

Geoff Pilling - 4 years, 5 months ago

@Geoff Pilling – No worries! Of course, there are some extra steps needed.

A minimum-distance network must be a tree on its vertices.
Any additional vertex must have at least $3$ edges (since otherwise a shorter network could be found).
Simple edge-counting shows that a minimum-distance between four vertices must have at most $2$ additional vertices.
Networks with $0$ and $1$ additional vertex can be seen as degenerate $2$ -additional vertex arrangements.

Now that we only have to consider $2$ -additional vertex arrangements, we can refer to the details of my proof.

Mark Hennings - 4 years, 5 months ago

Four towns, minimal roads

The answer is 5.46.

1 solution

0 pending reports