Building a cheap road
$begingroup$
The governor of Reniets (a land far, far away!) is known to be very stingy.
He has to build a road which connects all the five cities in the region, which are oddly arranged on the vertices of a regular pentagon (see the picture below).
Building a road is very expensive: the longer it is, the more it costs!
His first idea is to build five roads, each connecting a city to the center of the pentagon, then he realizes that it might not be optimal. In fact, he remembers that, years ago, his friend had to connect four towers, and the solution wasn't trivial!.
How long is the shortest path that connects all the five cities?
Notes:
assume that the side is long $1$ km.- I currently don't know the solution, I will accept the most convincing answer if no proof is given after some days.
- If you can generalize the solution to polygons of any number $n$ of sides, I will award a bounty (the amount depends on the quality of the work).
mathematics story optimization graph-theory
edited Apr 13 '17 at 12:50
Community♦
1
asked Jun 13 '15 at 8:38
leoll2leoll2
10.5k33077
$endgroup$
|
show 2 more comments
$begingroup$
The governor of Reniets (a land far, far away!) is known to be very stingy.
He has to build a road which connects all the five cities in the region, which are oddly arranged on the vertices of a regular pentagon (see the picture below).
Building a road is very expensive: the longer it is, the more it costs!
His first idea is to build five roads, each connecting a city to the center of the pentagon, then he realizes that it might not be optimal. In fact, he remembers that, years ago, his friend had to connect four towers, and the solution wasn't trivial!.
How long is the shortest path that connects all the five cities?
Notes:
assume that the side is long $1$ km.- I currently don't know the solution, I will accept the most convincing answer if no proof is given after some days.
- If you can generalize the solution to polygons of any number $n$ of sides, I will award a bounty (the amount depends on the quality of the work).
mathematics story optimization graph-theory
edited Apr 13 '17 at 12:50
Community♦
1
asked Jun 13 '15 at 8:38
leoll2leoll2
10.5k33077
$endgroup$
3
$begingroup$
An NP-Complete problem involving involving a open question. Nice light stuff for a Saturday morning!
$endgroup$
– Bob
Jun 13 '15 at 9:02
$begingroup$
@Bob What's the progress to this? Its evening here :)
$endgroup$
– Sharad Gautam
Jun 13 '15 at 9:08
$begingroup$
@Bob The actual NP-problem is the generalization to any set of points, not necessarily in a regular pattern. This problem is simply a pentagon, I doubt it is NP-complete; I don't know if it is for regular polygons too, the bounty is for that. Sharad, I've opened a chat room chat.stackexchange.com/rooms/24771/leoll2 for all those who want to ask anything about me.
$endgroup$
– leoll2
Jun 13 '15 at 9:09
$begingroup$
+1 Cool question. How do you come up with stuff like this?
$endgroup$
– JLee
Jun 13 '15 at 12:08
1
$begingroup$
@JLee Thanks! My original intention was to post the famous square puzzle, but it was already posted by another user, so I decided to add a variation. People seem to appreciate it, I already have few puzzle with similar features ready to be posted in the next days :)
$endgroup$
– leoll2
Jun 13 '15 at 12:20
|
show 2 more comments
$begingroup$
The governor of Reniets (a land far, far away!) is known to be very stingy.
He has to build a road which connects all the five cities in the region, which are oddly arranged on the vertices of a regular pentagon (see the picture below).
Building a road is very expensive: the longer it is, the more it costs!
His first idea is to build five roads, each connecting a city to the center of the pentagon, then he realizes that it might not be optimal. In fact, he remembers that, years ago, his friend had to connect four towers, and the solution wasn't trivial!.
How long is the shortest path that connects all the five cities?
Notes:
assume that the side is long $1$ km.- I currently don't know the solution, I will accept the most convincing answer if no proof is given after some days.
- If you can generalize the solution to polygons of any number $n$ of sides, I will award a bounty (the amount depends on the quality of the work).
mathematics story optimization graph-theory
edited Apr 13 '17 at 12:50
Community♦
1
asked Jun 13 '15 at 8:38
leoll2leoll2
10.5k33077
$endgroup$
The governor of Reniets (a land far, far away!) is known to be very stingy.
He has to build a road which connects all the five cities in the region, which are oddly arranged on the vertices of a regular pentagon (see the picture below).
Building a road is very expensive: the longer it is, the more it costs!
His first idea is to build five roads, each connecting a city to the center of the pentagon, then he realizes that it might not be optimal. In fact, he remembers that, years ago, his friend had to connect four towers, and the solution wasn't trivial!.
How long is the shortest path that connects all the five cities?
Notes:
assume that the side is long $1$ km.- I currently don't know the solution, I will accept the most convincing answer if no proof is given after some days.
- If you can generalize the solution to polygons of any number $n$ of sides, I will award a bounty (the amount depends on the quality of the work).
mathematics story optimization graph-theory
mathematics story optimization graph-theory
edited Apr 13 '17 at 12:50
Community♦
1
asked Jun 13 '15 at 8:38
leoll2leoll2
10.5k33077
edited Apr 13 '17 at 12:50
Community♦
1
asked Jun 13 '15 at 8:38
leoll2leoll2
10.5k33077
edited Apr 13 '17 at 12:50
Community♦
1
edited Apr 13 '17 at 12:50
Community♦
1
edited Apr 13 '17 at 12:50
Community♦
1
1
asked Jun 13 '15 at 8:38
leoll2leoll2
10.5k33077
asked Jun 13 '15 at 8:38
leoll2leoll2
10.5k33077
asked Jun 13 '15 at 8:38
leoll2leoll2
10.5k33077
10.5k33077
3
$begingroup$
An NP-Complete problem involving involving a open question. Nice light stuff for a Saturday morning!
$endgroup$
– Bob
Jun 13 '15 at 9:02
$begingroup$
@Bob What's the progress to this? Its evening here :)
$endgroup$
– Sharad Gautam
Jun 13 '15 at 9:08
$begingroup$
@Bob The actual NP-problem is the generalization to any set of points, not necessarily in a regular pattern. This problem is simply a pentagon, I doubt it is NP-complete; I don't know if it is for regular polygons too, the bounty is for that. Sharad, I've opened a chat room chat.stackexchange.com/rooms/24771/leoll2 for all those who want to ask anything about me.
$endgroup$
– leoll2
Jun 13 '15 at 9:09
$begingroup$
+1 Cool question. How do you come up with stuff like this?
$endgroup$
– JLee
Jun 13 '15 at 12:08
1
$begingroup$
@JLee Thanks! My original intention was to post the famous square puzzle, but it was already posted by another user, so I decided to add a variation. People seem to appreciate it, I already have few puzzle with similar features ready to be posted in the next days :)
$endgroup$
– leoll2
Jun 13 '15 at 12:20
|
show 2 more comments
3
$begingroup$
An NP-Complete problem involving involving a open question. Nice light stuff for a Saturday morning!
$endgroup$
– Bob
Jun 13 '15 at 9:02
$begingroup$
@Bob What's the progress to this? Its evening here :)
$endgroup$
– Sharad Gautam
Jun 13 '15 at 9:08
$begingroup$
@Bob The actual NP-problem is the generalization to any set of points, not necessarily in a regular pattern. This problem is simply a pentagon, I doubt it is NP-complete; I don't know if it is for regular polygons too, the bounty is for that. Sharad, I've opened a chat room chat.stackexchange.com/rooms/24771/leoll2 for all those who want to ask anything about me.
$endgroup$
– leoll2
Jun 13 '15 at 9:09
$begingroup$
+1 Cool question. How do you come up with stuff like this?
$endgroup$
– JLee
Jun 13 '15 at 12:08
1
$begingroup$
@JLee Thanks! My original intention was to post the famous square puzzle, but it was already posted by another user, so I decided to add a variation. People seem to appreciate it, I already have few puzzle with similar features ready to be posted in the next days :)
$endgroup$
– leoll2
Jun 13 '15 at 12:20
3
3
$begingroup$
An NP-Complete problem involving involving a open question. Nice light stuff for a Saturday morning!
$endgroup$
– Bob
Jun 13 '15 at 9:02
$begingroup$
An NP-Complete problem involving involving a open question. Nice light stuff for a Saturday morning!
$endgroup$
– Bob
Jun 13 '15 at 9:02
$begingroup$
@Bob What's the progress to this? Its evening here :)
$endgroup$
– Sharad Gautam
Jun 13 '15 at 9:08
$begingroup$
@Bob What's the progress to this? Its evening here :)
$endgroup$
– Sharad Gautam
Jun 13 '15 at 9:08
$begingroup$
@Bob The actual NP-problem is the generalization to any set of points, not necessarily in a regular pattern. This problem is simply a pentagon, I doubt it is NP-complete; I don't know if it is for regular polygons too, the bounty is for that. Sharad, I've opened a chat room chat.stackexchange.com/rooms/24771/leoll2 for all those who want to ask anything about me.
$endgroup$
– leoll2
Jun 13 '15 at 9:09
$begingroup$
@Bob The actual NP-problem is the generalization to any set of points, not necessarily in a regular pattern. This problem is simply a pentagon, I doubt it is NP-complete; I don't know if it is for regular polygons too, the bounty is for that. Sharad, I've opened a chat room chat.stackexchange.com/rooms/24771/leoll2 for all those who want to ask anything about me.
$endgroup$
– leoll2
Jun 13 '15 at 9:09
$begingroup$
+1 Cool question. How do you come up with stuff like this?
$endgroup$
– JLee
Jun 13 '15 at 12:08
$begingroup$
+1 Cool question. How do you come up with stuff like this?
$endgroup$
– JLee
Jun 13 '15 at 12:08
1
1
$begingroup$
@JLee Thanks! My original intention was to post the famous square puzzle, but it was already posted by another user, so I decided to add a variation. People seem to appreciate it, I already have few puzzle with similar features ready to be posted in the next days :)
$endgroup$
– leoll2
Jun 13 '15 at 12:20
$begingroup$
@JLee Thanks! My original intention was to post the famous square puzzle, but it was already posted by another user, so I decided to add a variation. People seem to appreciate it, I already have few puzzle with similar features ready to be posted in the next days :)
$endgroup$
– leoll2
Jun 13 '15 at 12:20
|
show 2 more comments
2 Answers
2
active
oldest
votes
$begingroup$
Here's the optimal solution for the pentagon:
As the only Steiner tree for this set of five points, it is the only locally minimal solution, hence it must be globally minimal.
For regular hexagons and above, just take the perimeter and remove one edge.
EDIT: Whoops I forgot to calculate the total path length. Brb.
EDIT2: The length of the tree in the pentagon is $${1over 2}sqrt{17+7sqrt{5}+sqrt{390+174sqrt{5}}} approx 3.891 ~text{km}.$$
For an $n$-gon ($n ge 6$) the total path length would obviously be $n-1~text{km}.$
answered Jun 13 '15 at 9:49
AnonAnon
2,5441718
$endgroup$
$begingroup$
Nice solution! Though, I don't understand the proof; it's not the only Steiner tree for those 5 points, my picture shows another example. Also, can you prove your statement about 6+ edges?
$endgroup$
– leoll2
Jun 13 '15 at 11:47
1
$begingroup$
+1 Nice answer, but if I lived in one of the 2 cities on the right, I'd be pissed because I'd need to go way out of my way to travel between them.
$endgroup$
– JLee
Jun 13 '15 at 12:07
$begingroup$
@leoll2 Your picture isn't a Steiner tree, because it contains angles smaller than 120°. There's always an easy local optimization when you have one of these angles. And no, I don't know how to prove the statement with n>5 edges, because there's usually more than one possible Steiner tree, for example in an octagon.
$endgroup$
– Anon
Jun 13 '15 at 12:29
1
$begingroup$
@leoll2 See Theorem 1 in Du, D.Z., Hwang, F.K. & Weng, J.F. Discrete Comput Geom (1987) 2: 65..
$endgroup$
– noedne
May 22 '18 at 21:43
1
$begingroup$
It should be written that their angles are 120 degrees.
$endgroup$
– Takahiro Waki
Aug 3 '18 at 15:15
|
show 1 more comment
$begingroup$
The first mistake is assuming that all five of these cities reside on a flat surface. They're likely on the surface of a sphere, such as a planet. But, we don't know which planet, or its radius. It could very likely not be Earth: "Reniets (a land far, far away!)". I propose the possibility that the planet has a radius small enough that all cities can be connected with a few inches of road, by projecting the regular polygon onto the surface of a sphere. Simply let half the circumference of the planet be very close to the distance from each city to the center of the polygon.
answered 2 hours ago
RinRin
1694
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "559"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fpuzzling.stackexchange.com%2fquestions%2f16341%2fbuilding-a-cheap-road%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Here's the optimal solution for the pentagon:
As the only Steiner tree for this set of five points, it is the only locally minimal solution, hence it must be globally minimal.
For regular hexagons and above, just take the perimeter and remove one edge.
EDIT: Whoops I forgot to calculate the total path length. Brb.
EDIT2: The length of the tree in the pentagon is $${1over 2}sqrt{17+7sqrt{5}+sqrt{390+174sqrt{5}}} approx 3.891 ~text{km}.$$
For an $n$-gon ($n ge 6$) the total path length would obviously be $n-1~text{km}.$
answered Jun 13 '15 at 9:49
AnonAnon
2,5441718
$endgroup$
$begingroup$
Nice solution! Though, I don't understand the proof; it's not the only Steiner tree for those 5 points, my picture shows another example. Also, can you prove your statement about 6+ edges?
$endgroup$
– leoll2
Jun 13 '15 at 11:47
1
$begingroup$
+1 Nice answer, but if I lived in one of the 2 cities on the right, I'd be pissed because I'd need to go way out of my way to travel between them.
$endgroup$
– JLee
Jun 13 '15 at 12:07
$begingroup$
@leoll2 Your picture isn't a Steiner tree, because it contains angles smaller than 120°. There's always an easy local optimization when you have one of these angles. And no, I don't know how to prove the statement with n>5 edges, because there's usually more than one possible Steiner tree, for example in an octagon.
$endgroup$
– Anon
Jun 13 '15 at 12:29
1
$begingroup$
@leoll2 See Theorem 1 in Du, D.Z., Hwang, F.K. & Weng, J.F. Discrete Comput Geom (1987) 2: 65..
$endgroup$
– noedne
May 22 '18 at 21:43
1
$begingroup$
It should be written that their angles are 120 degrees.
$endgroup$
– Takahiro Waki
Aug 3 '18 at 15:15
|
show 1 more comment
$begingroup$
Here's the optimal solution for the pentagon:
As the only Steiner tree for this set of five points, it is the only locally minimal solution, hence it must be globally minimal.
For regular hexagons and above, just take the perimeter and remove one edge.
EDIT: Whoops I forgot to calculate the total path length. Brb.
EDIT2: The length of the tree in the pentagon is $${1over 2}sqrt{17+7sqrt{5}+sqrt{390+174sqrt{5}}} approx 3.891 ~text{km}.$$
For an $n$-gon ($n ge 6$) the total path length would obviously be $n-1~text{km}.$
answered Jun 13 '15 at 9:49
AnonAnon
2,5441718
$endgroup$
$begingroup$
Nice solution! Though, I don't understand the proof; it's not the only Steiner tree for those 5 points, my picture shows another example. Also, can you prove your statement about 6+ edges?
$endgroup$
– leoll2
Jun 13 '15 at 11:47
1
$begingroup$
+1 Nice answer, but if I lived in one of the 2 cities on the right, I'd be pissed because I'd need to go way out of my way to travel between them.
$endgroup$
– JLee
Jun 13 '15 at 12:07
$begingroup$
@leoll2 Your picture isn't a Steiner tree, because it contains angles smaller than 120°. There's always an easy local optimization when you have one of these angles. And no, I don't know how to prove the statement with n>5 edges, because there's usually more than one possible Steiner tree, for example in an octagon.
$endgroup$
– Anon
Jun 13 '15 at 12:29
1
$begingroup$
@leoll2 See Theorem 1 in Du, D.Z., Hwang, F.K. & Weng, J.F. Discrete Comput Geom (1987) 2: 65..
$endgroup$
– noedne
May 22 '18 at 21:43
1
$begingroup$
It should be written that their angles are 120 degrees.
$endgroup$
– Takahiro Waki
Aug 3 '18 at 15:15
|
show 1 more comment
$begingroup$
Here's the optimal solution for the pentagon:
As the only Steiner tree for this set of five points, it is the only locally minimal solution, hence it must be globally minimal.
For regular hexagons and above, just take the perimeter and remove one edge.
EDIT: Whoops I forgot to calculate the total path length. Brb.
EDIT2: The length of the tree in the pentagon is $${1over 2}sqrt{17+7sqrt{5}+sqrt{390+174sqrt{5}}} approx 3.891 ~text{km}.$$
For an $n$-gon ($n ge 6$) the total path length would obviously be $n-1~text{km}.$
answered Jun 13 '15 at 9:49
AnonAnon
2,5441718
$endgroup$
Here's the optimal solution for the pentagon:
As the only Steiner tree for this set of five points, it is the only locally minimal solution, hence it must be globally minimal.
For regular hexagons and above, just take the perimeter and remove one edge.
EDIT: Whoops I forgot to calculate the total path length. Brb.
EDIT2: The length of the tree in the pentagon is $${1over 2}sqrt{17+7sqrt{5}+sqrt{390+174sqrt{5}}} approx 3.891 ~text{km}.$$
For an $n$-gon ($n ge 6$) the total path length would obviously be $n-1~text{km}.$
answered Jun 13 '15 at 9:49
AnonAnon
2,5441718
edited Jun 13 '15 at 10:56
answered Jun 13 '15 at 9:49
AnonAnon
2,5441718
answered Jun 13 '15 at 9:49
AnonAnon
2,5441718
answered Jun 13 '15 at 9:49
AnonAnon
2,5441718
2,5441718
$begingroup$
Nice solution! Though, I don't understand the proof; it's not the only Steiner tree for those 5 points, my picture shows another example. Also, can you prove your statement about 6+ edges?
$endgroup$
– leoll2
Jun 13 '15 at 11:47
1
$begingroup$
+1 Nice answer, but if I lived in one of the 2 cities on the right, I'd be pissed because I'd need to go way out of my way to travel between them.
$endgroup$
– JLee
Jun 13 '15 at 12:07
$begingroup$
@leoll2 Your picture isn't a Steiner tree, because it contains angles smaller than 120°. There's always an easy local optimization when you have one of these angles. And no, I don't know how to prove the statement with n>5 edges, because there's usually more than one possible Steiner tree, for example in an octagon.
$endgroup$
– Anon
Jun 13 '15 at 12:29
1
$begingroup$
@leoll2 See Theorem 1 in Du, D.Z., Hwang, F.K. & Weng, J.F. Discrete Comput Geom (1987) 2: 65..
$endgroup$
– noedne
May 22 '18 at 21:43
1
$begingroup$
It should be written that their angles are 120 degrees.
$endgroup$
– Takahiro Waki
Aug 3 '18 at 15:15
|
show 1 more comment
$begingroup$
Nice solution! Though, I don't understand the proof; it's not the only Steiner tree for those 5 points, my picture shows another example. Also, can you prove your statement about 6+ edges?
$endgroup$
– leoll2
Jun 13 '15 at 11:47
1
$begingroup$
+1 Nice answer, but if I lived in one of the 2 cities on the right, I'd be pissed because I'd need to go way out of my way to travel between them.
$endgroup$
– JLee
Jun 13 '15 at 12:07
$begingroup$
@leoll2 Your picture isn't a Steiner tree, because it contains angles smaller than 120°. There's always an easy local optimization when you have one of these angles. And no, I don't know how to prove the statement with n>5 edges, because there's usually more than one possible Steiner tree, for example in an octagon.
$endgroup$
– Anon
Jun 13 '15 at 12:29
1
$begingroup$
@leoll2 See Theorem 1 in Du, D.Z., Hwang, F.K. & Weng, J.F. Discrete Comput Geom (1987) 2: 65..
$endgroup$
– noedne
May 22 '18 at 21:43
1
$begingroup$
It should be written that their angles are 120 degrees.
$endgroup$
– Takahiro Waki
Aug 3 '18 at 15:15
$begingroup$
Nice solution! Though, I don't understand the proof; it's not the only Steiner tree for those 5 points, my picture shows another example. Also, can you prove your statement about 6+ edges?
$endgroup$
– leoll2
Jun 13 '15 at 11:47
$begingroup$
Nice solution! Though, I don't understand the proof; it's not the only Steiner tree for those 5 points, my picture shows another example. Also, can you prove your statement about 6+ edges?
$endgroup$
– leoll2
Jun 13 '15 at 11:47
1
1
$begingroup$
+1 Nice answer, but if I lived in one of the 2 cities on the right, I'd be pissed because I'd need to go way out of my way to travel between them.
$endgroup$
– JLee
Jun 13 '15 at 12:07
$begingroup$
+1 Nice answer, but if I lived in one of the 2 cities on the right, I'd be pissed because I'd need to go way out of my way to travel between them.
$endgroup$
– JLee
Jun 13 '15 at 12:07
$begingroup$
@leoll2 Your picture isn't a Steiner tree, because it contains angles smaller than 120°. There's always an easy local optimization when you have one of these angles. And no, I don't know how to prove the statement with n>5 edges, because there's usually more than one possible Steiner tree, for example in an octagon.
$endgroup$
– Anon
Jun 13 '15 at 12:29
$begingroup$
@leoll2 Your picture isn't a Steiner tree, because it contains angles smaller than 120°. There's always an easy local optimization when you have one of these angles. And no, I don't know how to prove the statement with n>5 edges, because there's usually more than one possible Steiner tree, for example in an octagon.
$endgroup$
– Anon
Jun 13 '15 at 12:29
1
1
$begingroup$
@leoll2 See Theorem 1 in Du, D.Z., Hwang, F.K. & Weng, J.F. Discrete Comput Geom (1987) 2: 65..
$endgroup$
– noedne
May 22 '18 at 21:43
$begingroup$
@leoll2 See Theorem 1 in Du, D.Z., Hwang, F.K. & Weng, J.F. Discrete Comput Geom (1987) 2: 65..
$endgroup$
– noedne
May 22 '18 at 21:43
1
1
$begingroup$
It should be written that their angles are 120 degrees.
$endgroup$
– Takahiro Waki
Aug 3 '18 at 15:15
$begingroup$
It should be written that their angles are 120 degrees.
$endgroup$
– Takahiro Waki
Aug 3 '18 at 15:15
|
show 1 more comment
$begingroup$
The first mistake is assuming that all five of these cities reside on a flat surface. They're likely on the surface of a sphere, such as a planet. But, we don't know which planet, or its radius. It could very likely not be Earth: "Reniets (a land far, far away!)". I propose the possibility that the planet has a radius small enough that all cities can be connected with a few inches of road, by projecting the regular polygon onto the surface of a sphere. Simply let half the circumference of the planet be very close to the distance from each city to the center of the polygon.
answered 2 hours ago
RinRin
1694
$endgroup$
add a comment |
$begingroup$
The first mistake is assuming that all five of these cities reside on a flat surface. They're likely on the surface of a sphere, such as a planet. But, we don't know which planet, or its radius. It could very likely not be Earth: "Reniets (a land far, far away!)". I propose the possibility that the planet has a radius small enough that all cities can be connected with a few inches of road, by projecting the regular polygon onto the surface of a sphere. Simply let half the circumference of the planet be very close to the distance from each city to the center of the polygon.
answered 2 hours ago
RinRin
1694
$endgroup$
add a comment |
$begingroup$
The first mistake is assuming that all five of these cities reside on a flat surface. They're likely on the surface of a sphere, such as a planet. But, we don't know which planet, or its radius. It could very likely not be Earth: "Reniets (a land far, far away!)". I propose the possibility that the planet has a radius small enough that all cities can be connected with a few inches of road, by projecting the regular polygon onto the surface of a sphere. Simply let half the circumference of the planet be very close to the distance from each city to the center of the polygon.
answered 2 hours ago
RinRin
1694
$endgroup$
The first mistake is assuming that all five of these cities reside on a flat surface. They're likely on the surface of a sphere, such as a planet. But, we don't know which planet, or its radius. It could very likely not be Earth: "Reniets (a land far, far away!)". I propose the possibility that the planet has a radius small enough that all cities can be connected with a few inches of road, by projecting the regular polygon onto the surface of a sphere. Simply let half the circumference of the planet be very close to the distance from each city to the center of the polygon.
answered 2 hours ago
RinRin
1694
edited 2 hours ago
answered 2 hours ago
RinRin
1694
answered 2 hours ago
RinRin
1694
answered 2 hours ago
RinRin
1694
1694
add a comment |
add a comment |
Thanks for contributing an answer to Puzzling Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fpuzzling.stackexchange.com%2fquestions%2f16341%2fbuilding-a-cheap-road%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
3
$begingroup$
An NP-Complete problem involving involving a open question. Nice light stuff for a Saturday morning!
$endgroup$
– Bob
Jun 13 '15 at 9:02
$begingroup$
@Bob What's the progress to this? Its evening here :)
$endgroup$
– Sharad Gautam
Jun 13 '15 at 9:08
$begingroup$
@Bob The actual NP-problem is the generalization to any set of points, not necessarily in a regular pattern. This problem is simply a pentagon, I doubt it is NP-complete; I don't know if it is for regular polygons too, the bounty is for that. Sharad, I've opened a chat room chat.stackexchange.com/rooms/24771/leoll2 for all those who want to ask anything about me.
$endgroup$
– leoll2
Jun 13 '15 at 9:09
$begingroup$
+1 Cool question. How do you come up with stuff like this?
$endgroup$
– JLee
Jun 13 '15 at 12:08
1
$begingroup$
@JLee Thanks! My original intention was to post the famous square puzzle, but it was already posted by another user, so I decided to add a variation. People seem to appreciate it, I already have few puzzle with similar features ready to be posted in the next days :)
$endgroup$
– leoll2
Jun 13 '15 at 12:20