Wizard Bait (Elegant but Extremely Difficult Math Problem)

Quote: dwheatley

Has anyone posted a link to the Steiner Tree pic yet?

Show Spoiler

http://en.wikipedia.org/wiki/File:Steiner_4_points.svg

My Master's dissertation had some work on Steiner trees.

I was too hasty. I should have given you more credit for this.

At the time I felt you were offering more of hint than a solution. But clearly it is a critical hint. I've now seen three distinct ways to solve the original unit square problem, and even a few solutions to the generalized problem of n points, and learned a thing or two myself in the process. Thanks for that!

Quote: Wizard

Good problem!

Let's say the four cities are at (0,0), (1,0), (1,1), and (0,1).

Wiz solution

Let point A have coordinate [1/(sqrt(12),1/2].
Let point B have coordinate [1-(1/sqrt(12),1/2].
Make roads from (0,0) and (0,1) to A.
Make roads from (1,0) and (1,1) to B.
Make road from A to B.
Total distance = 4*sqrt(1/3) + 1 - 2*sqrt(1/12) = 2.732050808.

In other words, the road network will look like an H on a diet shape.

You certainly nailed this problem suspiciously quickly. May I ask which, of the several approaches subsequently presented, if any, you used?

Quote: Ibeatyouraces

http://m.yelp.com/biz/wizard-of-suds-las-vegas

2.5 stars, lol.

There were two votes cast on this thread, five stars by the Wizard and zero by somebody else.

Are you the "somebody else" who diluted it to 2.5?

I'm assuming this based only on the content of your post, lol.

Quote: Transcend

Quote: dblanch256

(1) What is "the other" solution? [I'm choosing my words very carefully here]

(2) In what way is the solution (either one) "counter-intuitive" with respect to the original problem?

(3) Why (in simple English) must the optimal solution contain (or not contain) any curved segments?

(4) Why (in simple English) does the optimal solution beat the more obvious "X" pattern? Putting it another way,
what is it about the "X" pattern that is "wasteful" relative to the optimal pattern?

I surmise the other solution would be diagnol segments from the top and bottom corners with a vertical segment vs the optimal with a horizontal connection.

I don't exactly know why the answers would be counterintuitive besides that you stated they didn't need to be efficient which if one wanted to go from one town to the other that is connected via a side it would take more time than necessary. Also you didn't spend the entire 2.75 million so that may be cut out of future budgets, companies are always trying to save a buck. That and a traffic jam in the middle segment would be horrid at rush hour.

What is the quickest way between two points? A straight line. When trying to figure this problem out, I was racking my brain on how it could be done...I haven't done any sort of math in many years so I had to look a great deal up...first I thought of drawing a semi circle around the square but upon doing the math realized I would be way over budget, that and simply looking at the shapes I could have known that. I then decided that if I were to flip in the circle at two given corners I may be on to something an I with a parentheses on the top and bottom with the open ends facing away from connection with the I... But I realized this would also be not ideal because each curved segment would be longer than a mile. Upon this i deduced a triangle would better fit but I literally had no idea how to do the math for it and that is when I checked back here and saw something along those lines was posted. Oh well I tried.

Based on what I think the x pattern is relative because it allows the convergence of the two respective points from one side at an optimal rate but upon nearing the center it becomes wasteful having the extra distances connecting 4 points vs 2.

I may not by right...but I gave it the old college try...and honestly this problem really sparked my interest and was actually fun to try and deduce.

There is much to be said for the "good old college try" and I'm happy that you found it fun. Please read on to see several original (at least to me) and clever approaches and extended challenges on this topic.

Quote: Transcend

Reply would be just a fresh post in the thread, I don't see why you couldn't post a new problem in this thread... Considering it would be on topic

That sounds right. The magic phrase, I think, is "on topic". For extensions, I agree. For completely different challenges, I'm going to start new threads because I think its less confusing, overall. Thanks for the input.