Consider 4 houses located at the corners of a square with side length 1. We must build roads so that one can drive from any house to any other house along the roads. What is the minimum total length of road that needs to be built?
Just to get you started through the first few layers of solution, you can easily solve the problem with road length 3, connect 3 of the houses along sides of the square, and you have connected them all. You can do better with a 2√2 solution, by drawing in the diagonals of the square, this will connect all the houses to eachother by roads. As amazing as it might seem, you can do even better than that.
As a generalization of this problem, try solving it on a rectangle. You can further generalize it to other shapes, and even arbitrary distributions of points, but I wouldn't suggest it.
9 comments:
I can do it with length 2.73205... but I may be smoking the crack.
Yeah, that looks like the decimal expansion of the correct answer.
Wasn't sure if I was allowed to post the solution or if standard blog rules apply.
Kelley said the problem was too easy. I was crushed.
I would think that a good rule would be to just post your answer without giving any hints about how to find it, that seems like the reasonable thing to do anyway.
Clearly Kelley is too smart for us, you should have her solve the general case of what to do with an arbitrary distribution of points, I think you could publish that.
I just used first year calculus to solve this problem.
That is I knew the answer because Kory is a jerk who tells you the answer because he likes feeling smart, but I used calculus to PROVE IT.
(Yay for one-parameter optimization
Hey, I didn't tell you the answer, you were just present when Sean solved it.
Anyway, proving that it is optimal is actually pretty tough. I mean, you have probably proven that that is the optimal solution of that form, but you have not shown (I suspect) that it is the optimal form of a solution.
Proving in general that such a mechanism is optimal, but with only 4 points, you can quickly exhaust cases (there are 2, after symmetry arguments)
I realized, I need more words to make previous comment make sense. Yay quick rewrites after blogger forgets your comments:
Proving the general solution that the 'style' of solution is optimal is very hard, but with only 4 points ...
Post a Comment