## Sep 6 Steiner Trees

Four villages are located at the vertices of a square. How can you lay the minimum amount of road so that all of villages are connected? For the sake of easy communication let's say the square is 1 mile by 1 mile.

The immediate thought of putting a road on each of the four sides of the square, length 4 miles, can immediately be improved by only paving 3 of the sides. This still guarantees that you can still reach any of the villages, even if you have to go the long way around.

Ok, so length 3 miles to go. Possibly you can already see an improvement we can make. By crossing into the circle we can cut out some length. Let's look at two possible solutions:

The first doesn't actually improve anything, because I've just shifted along a line, but the second does slightly better. Two root two is about 2.8ish miles. However I've included both of these because it is a combination of both of these that has the best solution. Consider something like this:

Their is a straight bit remaining in the middle, but by titling the top and bottom lengths a bit we can possible save some length of road. I've labelled on the distance of 1/2 across the top because it is half of the distance across the square, but we don't know what slope will optimise the problem and so I've put the other length as just x. From this we can label some other things:

Since the total height is 1 mile and there is a length x at the top and the bottom, that only leaves a length of 1-2x for the middle portion. The diagonal length I have got from Pythagorus.

Since the total length is just made up of four identical diagonals and the straight portion, we can put this all together and simplify it slightly using some surd manipulation.

From here we are trying to make the total length y as small as possible while varying x, which is a classic optimisation problem (early first year A Level as an idea), it does require the chain rule to differentiate the square root, which comes up in second year. If it feels like I'm being ultra cautious to you as a competition mathematician, it is because I have just started with all of my new classes and I want to sign post some of this stuff. Let's take a crack at it:

Some second year of A Level calculus knowledge is needed here, but just accept the result of 2.732 miles if you haven't yet learned the chain rule.

As a pleasing result of this, the angle of slope for the bent lines is exactly 60 degrees ( as opposed to the 45 degrees of the previous best answer: the diagonal cross. It is worth noting that this is the optimal solution.

These structures are called Steiner Trees and they have lots of variations. Adding more points around in a polygon is a fun launching point, but one extension which you may be able to follow through if you know your chain rule is the three dimensional equivalent. Eight vertices form a cube: find the minimum line connect them all together. There is a picture of the idea below, but it is probably more fun to attempt it blind.

...