11
$\begingroup$

Is it possible to have 5 cities connected with roads, such that the shortest path between any pair of cities has the same length?

$\endgroup$
3
  • 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$
    – hexomino
    Commented Jan 9, 2023 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$ Commented Jan 9, 2023 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$
    – hexomino
    Commented Jan 9, 2023 at 12:58

3 Answers 3

21
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Just beat me. I was about to post the same answer. :-) $\endgroup$
    – fljx
    Commented Jan 9, 2023 at 13:29
13
$\begingroup$

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.
6-city solution with straight roads

$\endgroup$
10
  • 1
    $\begingroup$ Ooh I really like the last one with straight roads! Can it generalise to any number of cities? $\endgroup$ Commented Jan 9, 2023 at 14:26
  • $\begingroup$ @DmitryKamenetsky No, sadly it doesn't. I don't know of a straight road solution with more cities. $\endgroup$ Commented Jan 9, 2023 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$ Commented Jan 9, 2023 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$
    – Florian F
    Commented Jan 9, 2023 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$ Commented Jan 10, 2023 at 7:11
2
$\begingroup$

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.

$\endgroup$
7
  • 4
    $\begingroup$ Wouldn't the north pole be closer to the equator than to the south pole? $\endgroup$
    – hexomino
    Commented Jan 11, 2023 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$
    – Qami
    Commented Jan 11, 2023 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$
    – izrik
    Commented Jan 13, 2023 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$
    – izrik
    Commented Jan 13, 2023 at 14:22
  • $\begingroup$ @izrik You're absolutely right! I mis-visualized it. $\endgroup$
    – Qami
    Commented Jan 13, 2023 at 14:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.