Is it possible to have 5 cities connected with roads, such that the shortest path between any pair of cities has the same length?
$\begingroup$
$\endgroup$
3
asked Jan 9 at 12:26
-
2$\begingroup$ Are there any restrictions on the roads or their intersections? If not, I think there is an easy solution (which generalises to any number of cities). $\endgroup$– hexominoJan 9 at 12:46
-
$\begingroup$ No restrictions on roads - they can be curved. The only restriction on intersections is they cannot be disjoint (like bridges over another road). Looking forward to your solution! $\endgroup$– Dmitry KamenetskyJan 9 at 12:54
-
2$\begingroup$ I've hit the rep cap for today so I'll give someone else a chance to answer, interested to see what others make of it. $\endgroup$– hexominoJan 9 at 12:58
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
1
It is
possible!
Our approach:
Each city has a single road leaving it, with a length of n kilometers (for whatever n keeps the cities from overlapping). That road leads to one 5 way intersection. Therefore, to get from one city to another is always 2n km.
-
$\begingroup$ Just beat me. I was about to post the same answer. :-) $\endgroup$– fljxJan 9 at 13:29
$\begingroup$
$\endgroup$
10
StephenTG's answer is the most straightforward one, and it generalises to any number of cities. Here are some ideas for other solutions.
If roads are not necessarily straight,
then you can put in small zig-zags into any road to lengthen it by any amount. This allows for many alternative solutions. For example, you can start with any embedding of the complete graph with 5 nodes. As this is a non-planar graph, there will be at least one intersection. It is often relatively easy to place extra points which I'll call bogus intersections to some of the roads in such a way that all pairs of cities have paths with the same minimum number of intersections between them. Then it is just a matter of making each section of road the same length so that the city-to-city distances are all the same.
For example, if you draw the K5 graph with one crossing, add a bogus intersection on each of the 8 non-crossing edges. Every pair of cities then has a path between them with exactly one intersection (and none with less), so consists of two equal length sections.
Note that this method is only sure to work if the edges of your initial graph have at most one crossing. I'm not sure if it can be fully generalised.
With straight roads it is more tricky to find alternative solutions.
Here is one with 6 cities. Just remove any city for a 5-city solution.
answered Jan 9 at 14:17
-
1$\begingroup$ Ooh I really like the last one with straight roads! Can it generalise to any number of cities? $\endgroup$ Jan 9 at 14:26
-
$\begingroup$ @DmitryKamenetsky No, sadly it doesn't. I don't know of a straight road solution with more cities. $\endgroup$ Jan 9 at 14:28
-
$\begingroup$ Actually you can add another -X- for each rhombus to get a 9 city solution. Obviously you can keep doing that. $\endgroup$ Jan 9 at 14:32
-
5$\begingroup$ How would you place the X? If I understand what you propose the central city in the rhombus would be too close to the 2 others. $\endgroup$ Jan 9 at 15:50
-
2$\begingroup$ @DmitryKamenetsky Sure, but you'd have to put zigzags or curves in the blue roads to make them the same length as the black ones, otherwise the city to city distances won't all be equal. $\endgroup$ Jan 10 at 7:11
$\begingroup$
$\endgroup$
7
If the whole planet could be considered a prolate spheroid of the right shape, with no oceans in the way, you could put one at the north pole, one at the south pole, and the other three at equidistant points on the equator.
-
4$\begingroup$ Wouldn't the north pole be closer to the equator than to the south pole? $\endgroup$– hexominoJan 11 at 10:09
-
$\begingroup$ Good idea! But I think you mean oblate, not prolate, right? Otherwise, the three cities on the equator would be closer to each other than to the poles. en.wikipedia.org/wiki/Spheroid $\endgroup$– QamiJan 11 at 18:57
-
$\begingroup$ @Qami I don't think so. If you consider a perfect sphere, the circumference will be four times the distance from the equator to one of the poles. But that's too large for the points on the equator to be the same distance from each other and from the poles. The circumference should be three times the distance, instead of four, making it a prolate spheroid. $\endgroup$– izrikJan 13 at 14:21
-
$\begingroup$ @hexomino No, if we reduce the size of spheroid at the equator, then the north and south poles will be the same distance to the equator. $\endgroup$– izrikJan 13 at 14:22
-
$\begingroup$ @izrik You're absolutely right! I mis-visualized it. $\endgroup$– QamiJan 13 at 14:23