A natural, durable finish with minimal coats and fuss popular among woodworkers, flooring professionals, and furniture makers
Articles Forums Gallery Marketplace Videos

WoodCentral Forums

Est. 1998 — 27 years of woodworking knowledge

THE WOODRAT IS BACK!

Friday puzzle -- four towns

Posts

Friday puzzle -- four towns

#1

Friday puzzle -- four towns

Alex Y

Towns A, B, C, & D are positioned at the corners of a square, 100 miles on a side. The DOT has been tasked with designing a system of roadways to allow a resident of any of these towns to drive to any other.

At a planning meeting, engineer A asks "why don't we build a road between each pair of cities, minimizing the driving anyone will have to do to visit any other town?" The chairman responded that such a system, requiring 680 miles of road (since sqrt(2) = 1.4 in this area of the world), is too expensive.

Engineer B says "since A is the primary commercial center of these towns, and has most of the population, we could cut out half of the roads and just have a road from A to each of the other towns." The chairman replies that 340 miles of road is definitely better than 680, but wonders if there is a system of roads that could be built with less total mileage that will still connect all four towns.

What is the shortest such system of roads?

Re: Friday puzzle -- four towns

#2

Re: Friday puzzle -- four towns

Bill Earl

Such a system would also make the driving distance between any two towns the same.

Re: Friday puzzle -- four towns

#3

Re: Friday puzzle -- four towns

Steven McDaniel

And such a system of roads might require the extra expense of stop signs or a set of traffic lights, or perhaps a cloverleaf if there is a lot of traffic.

Re: Friday puzzle -- four towns

#4

Re: Friday puzzle -- four towns

Alex Y

I take it that you are thinking of a solution that requires only 280 miles of road? If so, that is indeed an improvement, but is not optimal.

Re: Friday puzzle -- four towns

#5

Re: Friday puzzle -- four towns

Alex Y

Steven, your practical concerns would also apply in the optimal case, but I don't think anyone has found that yet.

Re: Friday puzzle -- four towns

#6

Re: Friday puzzle -- four towns

Bill Earl

But wouldn't the optimal case require twice as many traffic lights?

Re: Friday puzzle -- four towns

#7

  Yes, it would. Very good


Re: Friday puzzle -- four towns

#8

I've seen this in 3D

Bill Earl

The topologists get all in a lather about it. But the math makes my head go 'pop'.

Re: Friday puzzle -- four towns

#9

Solution (a soapy one) *LINK*

Alex Y

Good on Bill for getting this one.

There are a few road systems that are shorter than the 340-mile A-to-every-town system, such as a "U" going from A to D to C to B (assuming the towns are lettered clockwise from the upper left) at 300 miles, and the two diagonals (turning at the center if needed to reach the destination) at 280 miles.

However the optimum is an "H" squeezed in at the middle so that the "verticals" are slanted 30 degrees toward the center. The length of this system is 100*(1+sqrt(3)) = 273 miles.

This is called a Steiner Tree. Each of the intersections has roads meeting at 120 degree angles. It provides a (local) minimum-length path connecting a series of points. Rather than trying to draw the picture or explain more, I'll refer you to this entertaining You-Tube explanation, complete with a soap-bubble demonstration. [Bill: is this the one to which you referred?]


YouTube explanation and illustration

Re: Friday puzzle -- four towns

#10

Re: Solution (a soapy one) *LINK*

Bill Earl

I hadn't seen that one. I had seen experiments with minimal surface bubbles on 3 dimensional forms, but I couldn't figure out how to apply it to the 2 dimensional problem. The plexiglass sides on his form turn it into a "2-1/2D" problem. Very clever!


http://www.miqel.com/fractals_math_patterns/visual-math-minimal-surfaces.html

👍 This page answered my questions

Your vote helps other woodworkers quickly find the answers and techniques that actually work in the shop.