5 houses are located on the vertices of a regular pentagon with side length 2 km.
Find the length of the shortest road (in km) that needs to be built such that all 5 houses are connected to one another by this road.
Give your answer to 3 decimal places.
Clarification: The road is a network of straight lines.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
It is known that the steiner tree for 5 points has 3 steiner points. So we know that the steiner tree would look something like this:
To find the steiner tree, we make use of transformations:
Our primary objective is to find the position of O
First, rotate line A B 60 degrees about point A . Since we want to minimise O P + P A + P B for any randomly chosen O , O P + P A + P B = O J (a straight line)
Do the same for side C D .
Now the problem is reduced to finding the steiner tree of a triangle. This would enable us to find O :
To do so, we can employ similar techniques. Rotate line K J about point K by 60 degrees
It can be seen that the length of steiner tree would be the length of M L , which is the height of equilateral triangle K J M plus the height of triangle L K J . Through symmetry and some trigonometry, we can find that the length of the steiner tree is:
3 ( 1 + 2 cos 1 2 ) + 5 + 2 5 − 2 sin 1 2 = 7 . 7 8 2 3 1 3 6 4 6 6 5
In response to Mark's comment below:
Point O , such that L , O , O ′ and M are collinear can be found through the intersection of line L M and the excircle of triangle K J M . This is because O K M J is a cyclic quadrilateral, concluded by noticing that ∠ K M O = ∠ O J K through triangle congruity. The same technique can be applied to find the positions of the rest of the steiner points
Thank you, Julian! Complete with the construction manual. When I myself get the answer through trial and error method, with a lot of shape of path on the way.
Certainly the distance LM is the minimum possible network length, but you need to draw a few circles to show that this minimum distance can actually be achieved... How do you choose O such that L, O "rotated O" and M are collinear? Similarly, how do you choose P so that O, P, "rotated P" and J are collinear?
Thank you. That completes an excellent proof (+1).
can this be generalised to n dimensions?
Log in to reply
sorry, an n gon
Log in to reply
Certainly. The regular n -gon problem, for all n except 7 to 1 2 inclusive, was handled by a paper written in 1934 (sadly, in Czech), and a more recent paper handles the missing cases. It seems that 7 to 1 2 is handled by deleting a single side.
This MSE link gives a little more information.
Problem Loading...
Note Loading...
Set Loading...
A Steiner point is a road junction where three roads meet, each making an angle of 1 2 0 ∘ with the others. The shortest road network is one containing 3 = 5 − 2 Steiner points. One symmetrical network is below.
Using the Sine Rule four times, we have a b b + c c + d = = = = sin 1 2 0 ∘ 2 sin 4 2 ∘ sin 1 2 0 ∘ 2 sin 1 8 ∘ sin 6 0 ∘ 2 sin 5 4 ∘ sin 6 0 ∘ 2 sin 6 6 ∘ and so the shortest road network has length 2 a + 2 b + 2 c + d = 7 . 7 8 2 3 1 km.