A tale of four cities problem
Poll
 | 4 votes (44.44%) | ||
| No votes (0%) | |||
| | 5 votes (55.55%) | ||
| No votes (0%) | |||
| No votes (0%) | |||
| | 1 vote (11.11%) | ||
| | 1 vote (11.11%) | ||
| | 1 vote (11.11%) | ||
| No votes (0%) | |||
| | 3 votes (33.33%) |
9 members have voted
March 1st, 2019 at 7:41:32 AM
permalink
You are in charge of transportation of a square state with side length of 200 kilometers. There is a town in each corner of the state. Your goal is to connect the four towns with roads. How can you do this with the least total miles of roads?
Let the record show that I can't prove my answer is optimal. For the beer, you will have to match my answer. For a fancy cocktail, like sex on the beach, beat my answer. I will submit what I believe to be the best answer to OD by PM in the interests of being above reproach.
As usual, anyone who has won a beer is on a 24-hour hold.
The question for the poll is what is the basic shape of the roads?
Let the record show that I can't prove my answer is optimal. For the beer, you will have to match my answer. For a fancy cocktail, like sex on the beach, beat my answer. I will submit what I believe to be the best answer to OD by PM in the interests of being above reproach.
As usual, anyone who has won a beer is on a 24-hour hold.
The question for the poll is what is the basic shape of the roads?
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
March 1st, 2019 at 8:07:33 AM
permalink
I've recently returned to this forum. Is bigotry no longer allowed in polls?
I would imagine a 90 degree square or diamond shape would be the shortest. Closer to the center of the four borders.
I dunno...someone smarter can answer.
I would imagine a 90 degree square or diamond shape would be the shortest. Closer to the center of the four borders.
I dunno...someone smarter can answer.
March 1st, 2019 at 8:18:37 AM
permalink
I'm going to go with the obvious (which means it's probably not optimal) and say connect the cities in the opposite corners, creating an 'X.' This would require 400 * 21/2 or roughly 566 miles of road.
"Dealer has 'rock'... Pay 'paper!'"
March 1st, 2019 at 8:34:28 AM
permalink
It's going to look like an "H" with bent sides, either upright or on its side.. Sort of 》=《. That's because the crossbar will be less road paved overall than needed by 2 hypotenuses.
With sides 200, an unbent "H" is 600 km roads paved. A full "X" is approx. 565.68 km of paving. But the shape I described is going to be less than either for some series of answers because of the crossbar duplication. I'm just not sure how to calculate the maximum saving of road length.
For example, if the bent sides represent 4 30-60-90 triangles, the length of each bent side is
a = x = road not needed.
b = (x*sqrt3) = 100 = half the distance to the center
c = 2x = top or bottom leg of diagonal
so a = x = 57.735
115.470 x 2
x2 sides
= 461.88 km.
The remainder crossbar is
200 - (2x57.735) = 200 - 115.47
= 84.53 k.
Total paved length is 546.41 km
But maybe optimum is with a top angle of 31°, or 29°, or some fraction of those or another angle. There's going to be a bell curve of better answers, starting with 1° off "X", ending somewhere short of the savings of paving an "X", in the direction of straight sides. What the top point of that bell is, I don't know.
Edit: Doing spot checks on some other angles seems to indicate that the arm angles should be 30° from each corner, leaving the answer above, corrected to two places. No other edits. So that's my final answer.
With sides 200, an unbent "H" is 600 km roads paved. A full "X" is approx. 565.68 km of paving. But the shape I described is going to be less than either for some series of answers because of the crossbar duplication. I'm just not sure how to calculate the maximum saving of road length.
For example, if the bent sides represent 4 30-60-90 triangles, the length of each bent side is
a = x = road not needed.
b = (x*sqrt3) = 100 = half the distance to the center
c = 2x = top or bottom leg of diagonal
so a = x = 57.735
115.470 x 2
x2 sides
= 461.88 km.
The remainder crossbar is
200 - (2x57.735) = 200 - 115.47
= 84.53 k.
Total paved length is 546.41 km
But maybe optimum is with a top angle of 31°, or 29°, or some fraction of those or another angle. There's going to be a bell curve of better answers, starting with 1° off "X", ending somewhere short of the savings of paving an "X", in the direction of straight sides. What the top point of that bell is, I don't know.
Edit: Doing spot checks on some other angles seems to indicate that the arm angles should be 30° from each corner, leaving the answer above, corrected to two places. No other edits. So that's my final answer.
Last edited by: beachbumbabs on Mar 1, 2019
If the House lost every hand, they wouldn't deal the game.
March 1st, 2019 at 8:45:47 AM
permalink
You can build a road that is U shaped, 200km from A to B, another 200km from B to C, and another 200 from C to D.
That's fine if you happen to be going from A to B, or B to C, or C to D. Unfortunately, it's a 600km trip from A to D along this U shaped highway.
Or you can ...
Mind you, this assumes that the four cities have no area to speak of, and that there's nothing else in the state.
Of course, having grown up in New Jersey, this is not far from what we thought of the "square" states out west before venturing out to see them. :D
That's fine if you happen to be going from A to B, or B to C, or C to D. Unfortunately, it's a 600km trip from A to D along this U shaped highway.
Or you can ...
... build two highways, X shaped. Since it's (( 200^2 ) + ( 200^2 )) ^ 0.5 = 282.8km from corner to corner, the total road surface being built is about 565.6km. 34.4km less than the U shape, and far more efficient.
With this highway, it's 141.4km from any city to the intersection of the two roads, or 282.8km from any city to any other.
(I suggest being the guy who owns the gas / rest stop at the intersection.)
With this highway, it's 141.4km from any city to the intersection of the two roads, or 282.8km from any city to any other.
(I suggest being the guy who owns the gas / rest stop at the intersection.)
Mind you, this assumes that the four cities have no area to speak of, and that there's nothing else in the state.
Of course, having grown up in New Jersey, this is not far from what we thought of the "square" states out west before venturing out to see them. :D
I invented a few casino games. Info:
http://www.DaveMillerGaming.com/ —————————————————————————————————————
Superstitions are silly, irrational, childish rituals, born out of fear of the unknown. But how much does it cost to knock on wood? 😁
March 1st, 2019 at 9:12:55 AM
permalink
Sounds like typical local government incompetence. Minimizing road miles rather than travel time between towns.Quote: WizardYou are in charge of transportation of a square state with side length of 200 kilometers. There is a town in each corner of the state. Your goal is to connect the four towns with roads. How can you do this with the least total miles of roads?
Let the record show that I can't prove my answer is optimal. For the beer, you will have to match my answer. For a fancy cocktail, like sex on the beach, beat my answer. I will submit what I believe to be the best answer to OD by PM in the interests of being above reproach.
As usual, anyone who has won a beer is on a 24-hour hold.
The question for the poll is what is the basic shape of the roads?
The race is not always to the swift, nor the battle to the strong; but that is the way to bet.
March 1st, 2019 at 9:55:34 AM
permalink
I submitted my answer before reading anyone's spoiler.
Sigh, now having done so, I think Babs is on the right track, although she provided a concept only, with no math.
Therefore, here's some math...
Edit: Babs originally didn’t have any math.
Sigh, now having done so, I think Babs is on the right track, although she provided a concept only, with no math.
Therefore, here's some math...
Babs' idea of the bent H, or 》=《 seems right. Her example of a straight H uses the same 600km as my U shape, but the bent H is a good compromise to my X shape.
My knee-jerk thinking says that if all 5 segments are the same length, you'll get the optimal, smallest amount of road to build.
After playing with Excel, I find that that is not the case. Not even close.
In the 》=《 design, the optimal length of the crossbar is 84.50km, while the 4 legs are 115.48km, producing a road with a total length of 546.410km.
I'm sure there's a trig type function that would have made this easier, but I used columns in Excel and brute force to get to the estimate:
Col A = 75 thru 95 in .5 steps.
Col B = (200-A_)/2 to find how far from each border the two intersections will be.
Col C = B^2 This is one side of the leg's triangle, squared.
Col D = sqrt(C_+10000) Note 10000 is the height squared. This produces the length of each leg.
Col E = D_ * 4 + A_ for the total road length.
A short trip, one that doesn’t need the crossbar, is only 230.95km and a long trip is 315.46km.
Of course, this will create a rivalry between the owners of the two gas/rest stops at the intersections. The more successful one will be the one with a casino that allows slot points to be used for gas, and has NO PARKING FEES! (but I digress...)
My knee-jerk thinking says that if all 5 segments are the same length, you'll get the optimal, smallest amount of road to build.
After playing with Excel, I find that that is not the case. Not even close.
In the 》=《 design, the optimal length of the crossbar is 84.50km, while the 4 legs are 115.48km, producing a road with a total length of 546.410km.
I'm sure there's a trig type function that would have made this easier, but I used columns in Excel and brute force to get to the estimate:
Col A = 75 thru 95 in .5 steps.
Col B = (200-A_)/2 to find how far from each border the two intersections will be.
Col C = B^2 This is one side of the leg's triangle, squared.
Col D = sqrt(C_+10000) Note 10000 is the height squared. This produces the length of each leg.
Col E = D_ * 4 + A_ for the total road length.
A short trip, one that doesn’t need the crossbar, is only 230.95km and a long trip is 315.46km.
Of course, this will create a rivalry between the owners of the two gas/rest stops at the intersections. The more successful one will be the one with a casino that allows slot points to be used for gas, and has NO PARKING FEES! (but I digress...)
Edit: Babs originally didn’t have any math.
Last edited by: DJTeddyBear on Mar 1, 2019
I invented a few casino games. Info:
http://www.DaveMillerGaming.com/ —————————————————————————————————————
Superstitions are silly, irrational, childish rituals, born out of fear of the unknown. But how much does it cost to knock on wood? 😁
March 1st, 2019 at 10:56:31 AM
permalink
Thanks for the responses so far. I'd like to say that to get full credit I want to see a solution that for the given type of road shape, the details are optimal. Not just using goalseek in Excel, or some similar product.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
March 1st, 2019 at 11:30:20 AM
permalink
Presumably roads can be joined at any place they touch?Quote: WizardYou are in charge of transportation of a square state with side length of 200 kilometers. There is a town in each corner of the state. Your goal is to connect the four towns with roads. How can you do this with the least total miles of roads?
Let the record show that I can't prove my answer is optimal. For the beer, you will have to match my answer. For a fancy cocktail, like sex on the beach, beat my answer. I will submit what I believe to be the best answer to OD by PM in the interests of being above reproach.
As usual, anyone who has won a beer is on a 24-hour hold.
The question for the poll is what is the basic shape of the roads?
Psalm 25:16
Turn to me and be gracious to me, for I am lonely and afflicted.
Proverbs 18:2
A fool finds no satisfaction in trying to understand, for he would rather express his own opinion.
March 1st, 2019 at 11:37:02 AM
permalink
Here's a wrong answer:
I tried to use the H shape, but rounded the heights, so the roads looked like this:
)--(
I used excel, inputting chord length, chord height, radius, arc angle in radians, and used that to compute the arc length. (I pulled all the formulas off of google.) Using every possible chord height (in .5km increments), the optimal amount of total road used was 561.39km. The heights of the rounded 'H' are each 220.69km, and the horizontal cross road is 120km.
Less than an X shape, but not the best answer so far.
I tried to use the H shape, but rounded the heights, so the roads looked like this:
)--(
I used excel, inputting chord length, chord height, radius, arc angle in radians, and used that to compute the arc length. (I pulled all the formulas off of google.) Using every possible chord height (in .5km increments), the optimal amount of total road used was 561.39km. The heights of the rounded 'H' are each 220.69km, and the horizontal cross road is 120km.
Less than an X shape, but not the best answer so far.
Just trying to stay positive
March 1st, 2019 at 12:00:52 PM
permalink
Since I have known of this problem before, I must recuse myself. However, once you guys are done working on it, reward yourself with this clip (spoiler!):
https://youtu.be/dAyDi1aa40E?t=250
https://youtu.be/dAyDi1aa40E?t=250
March 1st, 2019 at 12:05:29 PM
permalink
Quote: WizardThanks for the responses so far. I'd like to say that to get full credit I want to see a solution that for the given type of road shape, the details are optimal. Not just using goalseek in Excel, or some similar product.
Which means that, once again, Babs has the right answer, but not the definitive proof, correct Wizard? And once again, the goalposts move away from the Babs beer. (Edit: I'm wrong about the goalposts moving, perhaps. I don't know if my answer equals or beats the Wizard's. The POLL asked the best shape, but did not qualify for the beer.)
I would submit that the 30° angle is the correct answer for all squares. For other rectangles, the angle could change, but not exceed 45° nor fall to 0 (all angles measured from the shorter side). The crossbar of the H should always parallel the longer side of the rectangle. These rules are all reflective of the ratio of the hypotenuse to the shorter side of a right triangle.
If the House lost every hand, they wouldn't deal the game.
March 1st, 2019 at 1:37:28 PM
permalink
Here is an idea for the proof.
First consider the shortest roads between three points. It transpires (ignoring weird cases where going AB and BC are shorter) the point is such that the angles of the three roads AF, BF, CF all meet at 120 degrees. (I can prove it if needs be but the rough proof is to consider strings where they all pull a ring at point F; then by symmetry the net force has to be 0; so the angles have to be equal.)
Now consider the square ABCD and roads directly to the centre (E). Thus the initial idea is roads AE BE CE and DE. Then consider the three points A B and E. The set of roads at 120 degrees is shorter than AE+BE. So construct a point F so the roads are AF BF and EF where the angles at F are 120 degrees. Similarly construct G for C and D.
This leaves the roads AE BE EF FC FD as a local minimum. However this set of roads goes through the centre of the square so symmetry suggest this is one of two solutions (the other solution joins BCE and ADF instead).
First consider the shortest roads between three points. It transpires (ignoring weird cases where going AB and BC are shorter) the point is such that the angles of the three roads AF, BF, CF all meet at 120 degrees. (I can prove it if needs be but the rough proof is to consider strings where they all pull a ring at point F; then by symmetry the net force has to be 0; so the angles have to be equal.)
Now consider the square ABCD and roads directly to the centre (E). Thus the initial idea is roads AE BE CE and DE. Then consider the three points A B and E. The set of roads at 120 degrees is shorter than AE+BE. So construct a point F so the roads are AF BF and EF where the angles at F are 120 degrees. Similarly construct G for C and D.
This leaves the roads AE BE EF FC FD as a local minimum. However this set of roads goes through the centre of the square so symmetry suggest this is one of two solutions (the other solution joins BCE and ADF instead).
March 1st, 2019 at 1:48:32 PM
permalink
So after reading Babs' answer and Wiz's response above, I figured that I should be able to dust off my old Calc and Trig books and solve this. This solution crossed my mind before I gave my first answer, but I didn't have the time or resources then to tackle it at that point.
So, assuming the "slant H" shape, the the road is the total of the four angled lines plus the horizontal line. Since the state is symmetrical, we can just focus on half of the state, and double our answer at the end. So, all we need to do now is come up with a function that defines the length of road. Once we have that, we can take the first derivative of that function and set the result equal zero. Then by solving that equation, we can determine the minimum road length. Here's a crude drawing of this
From this, we see that the length of road is equal to the total length of the two angled lines plus the left segment of the horizontal line.
In terms of angle 'a,' the total length L = 2(100*sec a) + (100 - 100*tan a). Let's divide out the 100 to get a simplified:
L = 2(sec a) + 1 - tan a
Taking the first deravitive, we get
d/da = 2(sec a * tan a) - sec2a
Now, set d/da = 0 and solve for a:
sec2a = 2(sec a * tan a)
divide out sec a from both sides to get:
sec a = 2(tan a)
substitute the right angle triangle sides (Opp, Adj, Hyp) for the trig ratios, and you get:
H/A = 2 O/A
multiply both sides by A and rearrange, and you get:
O/H = 1/2 = sin a
So, a = 30°, just like Babs said! :)
Thus, L = 200*sec 30° + 100 - 100* tan 30°, yielding L = 273.2
Double that and you get the total paved km to be: 546.4
So, assuming the "slant H" shape, the the road is the total of the four angled lines plus the horizontal line. Since the state is symmetrical, we can just focus on half of the state, and double our answer at the end. So, all we need to do now is come up with a function that defines the length of road. Once we have that, we can take the first derivative of that function and set the result equal zero. Then by solving that equation, we can determine the minimum road length. Here's a crude drawing of this
From this, we see that the length of road is equal to the total length of the two angled lines plus the left segment of the horizontal line.
In terms of angle 'a,' the total length L = 2(100*sec a) + (100 - 100*tan a). Let's divide out the 100 to get a simplified:
L = 2(sec a) + 1 - tan a
Taking the first deravitive, we get
d/da = 2(sec a * tan a) - sec2a
Now, set d/da = 0 and solve for a:
sec2a = 2(sec a * tan a)
divide out sec a from both sides to get:
sec a = 2(tan a)
substitute the right angle triangle sides (Opp, Adj, Hyp) for the trig ratios, and you get:
H/A = 2 O/A
multiply both sides by A and rearrange, and you get:
O/H = 1/2 = sin a
So, a = 30°, just like Babs said! :)
Thus, L = 200*sec 30° + 100 - 100* tan 30°, yielding L = 273.2
Double that and you get the total paved km to be: 546.4
"Dealer has 'rock'... Pay 'paper!'"
March 1st, 2019 at 3:54:04 PM
permalink
Quote: beachbumbabsWhich means that, once again, Babs has the right answer, but not the definitive proof, correct Wizard? And once again, the goalposts move away from the Babs beer.
Yes, that is pretty much the case. Lest, you feel I'm being unfair, I think most here can vouch that I like to see winners show their work to get full credit. I know it is difficult conveying a full solution with a keyboard, so I don't need to see every step. Glorified trial and error is not the kind of "work" I like to see.
Hint: Calculus is the perfect tool for problems like this, and we all know much I love calculus.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
March 1st, 2019 at 5:17:24 PM
permalink
I agree with Babs answer (although I hadn't read it before answering). I'm not sure you need calculus to prove it, except you can think of little triangles...and prove the derivitave needs to be zero.Quote: Wizard...Hint: Calculus is the perfect tool for problems like this...
Just consider the base AB along the x-asis so A=(0,0) B=(200,0) and the center is at O=(100,100). The roads meet at Y=(100,y).
It is easier to think of triangles and how various lengths change as y changes.
As y increases the length of the road to the centre merely decreases by y (actually YO = 100-y).
Consider similar triangles and the angle BAY. (You actually need to look at a small triangle Y Y' and Z=a point on AY extended where Y Z Y' is a right angles.)
Angle(Y Y' Z) = Angle(BAY), and the length Y Y' is y (i.e. how long the road to the center changed) and the length Y Z is (for small triangles) how long the road AY got longer.
Since Y Z = Y Y' * Sin ( Y Y' Z )= Y Y' * Sin (BAY)
There are two roads (AY and BY) so the total length of these increase by 2 * { Y Y' * Sin (BAY) }.
Thus the total roads change by 2 y Sin(BAY) - y.
This is zero when Sin(BAY)= 1/2 i.e. when BAY = 30 degrees.
Thus AYB = 120 degrees.
Thus AY = 2 y and 100 = SQRT (2y*2y - y*y) = SQRT(3 y^2). So y = 100 / SQRT(3).
Total length of all roads = 4 * 2y + 2 * (100-y) = 200+6y = 200 + 600/SQRT(3) = 200 * (SQRT(3)+1) = 546.102.
It is easier to think of triangles and how various lengths change as y changes.
As y increases the length of the road to the centre merely decreases by y (actually YO = 100-y).
Consider similar triangles and the angle BAY. (You actually need to look at a small triangle Y Y' and Z=a point on AY extended where Y Z Y' is a right angles.)
Angle(Y Y' Z) = Angle(BAY), and the length Y Y' is y (i.e. how long the road to the center changed) and the length Y Z is (for small triangles) how long the road AY got longer.
Since Y Z = Y Y' * Sin ( Y Y' Z )= Y Y' * Sin (BAY)
There are two roads (AY and BY) so the total length of these increase by 2 * { Y Y' * Sin (BAY) }.
Thus the total roads change by 2 y Sin(BAY) - y.
This is zero when Sin(BAY)= 1/2 i.e. when BAY = 30 degrees.
Thus AYB = 120 degrees.
Thus AY = 2 y and 100 = SQRT (2y*2y - y*y) = SQRT(3 y^2). So y = 100 / SQRT(3).
Total length of all roads = 4 * 2y + 2 * (100-y) = 200+6y = 200 + 600/SQRT(3) = 200 * (SQRT(3)+1) = 546.102.
March 1st, 2019 at 8:46:11 PM
permalink
I don't understand how the soap KNOWS how to solve this problem.
March 1st, 2019 at 8:52:59 PM
permalink
Sounds like Mike is talking about the Excel spreadsheet that I discribed in my second post on page 1. But that’s OK. I kinda new that he would not like that kind of “proof.”Quote: Wizard... Glorified trial and error is not the kind of "work" I like to see.
I invented a few casino games. Info:
http://www.DaveMillerGaming.com/ —————————————————————————————————————
Superstitions are silly, irrational, childish rituals, born out of fear of the unknown. But how much does it cost to knock on wood? 😁
March 1st, 2019 at 9:39:56 PM
permalink
I have to give the beer to Charlie on this one. If he is claiming his solution didn't use calculus, I would claim it did, but avoiding calculus terminology. He can transfer his beer to Barbara, if he wishes.
Can anyone find a web page that gives solutions for higher order regular n-gons?
Can anyone find a web page that gives solutions for higher order regular n-gons?
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
March 2nd, 2019 at 12:08:24 AM
permalink
apparently for an octagon it's just the perimeter. I would guess anything with more sides would be the same.
March 2nd, 2019 at 1:53:38 AM
permalink
Yes - please let Barbara have my beer when you all meet up in Spring.Quote: WizardI have to give the beer to ... Barbara, if he wishes.
Can anyone find a web page that gives solutions for higher order regular n-gons?
I've only just stumbled across https://www.unige.ch/~gander/Preprints/BDM56-GanderE.pdf this morning - it looks very interesting and has the proof for square (s 5.1) and pentagon (s 5.2). Essentially he introduces Steiner Points and shows various lemmas (I haven't used that word since university!). As a hint, if you don't want to cheat, you need 3 junctions for a pentagon.
March 2nd, 2019 at 5:16:43 AM
permalink
Quote: sodawaterI don't understand how the soap KNOWS how to solve this problem.
Thanks for your comment! I was getting very sad over the lack of shared enthusiasm concerning the insanity of soap-based mathematics!
March 2nd, 2019 at 7:52:28 AM
permalink
Interesting stuff. Reminds me of the travelling salesman problem.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
March 2nd, 2019 at 8:28:10 PM
permalink
Quote: WizardYes, that is pretty much the case. Lest, you feel I'm being unfair, I think most here can vouch that I like to see winners show their work to get full credit. I know it is difficult conveying a full solution with a keyboard, so I don't need to see every step. Glorified trial and error is not the kind of "work" I like to see.
Hint: Calculus is the perfect tool for problems like this, and we all know much I love calculus.
If the House lost every hand, they wouldn't deal the game.
