100

Maths Problem: Connect the towns solution (Motorway Problem)


Hello, Everyone! Last time, I gave you this problem: you have four towns, in a one-mile square– what is the minimum amount of road you need to connect those four towns together? Well, let’s look at a few of the possibilities. So we could connect the towns together like this, so every town is connected to every other town. Now, each side of the square has length one, and the diagonals– well, with a quick bit of Pythag you can work out that the diagonals are root two–the square root of two. So all together, this has length 4 plus 2 root 2– that’s about 6.82. We could connect the towns together in a big circle, perhaps. I’ve already told you the diagonal has a length of root two. So the circle has a length of pi root 2. That’s about 4.44. We could connect the towns together in a big square. That has length 4. Even better than that, we could connect them in that sort of U shape, which has length 3, but it’s not a very efficient way, especially to get from A to B. It’s not a very efficient way to get around. Perhaps a slightly better answer would be to connect them into a H, Which would still have length 3, but perhaps slightly more efficient. But this isn’t the minimum answer, either. You might have thought the smallest answer would have been a cross. So those two diagonals–well, the diagonals have length root two, so this has a length of 2 root 2, which is about 2.82. That’s certainly the smallest answer so far, but it isn’t the minimum solution. Let’s find out what is. Working out the minimum length of a problem like this is called ‘calculus of variations,’ and can be quite difficult. But this is where nature is going to help us. I’ve had a prop made for me. It’s actually two layers of Perspex® with four pegs in it. And these four pegs are going to represent our four towns. And I’m going to dip this into this bowl of soapy water. And what it will do, is it will create a film of soap and this soap film will naturally try to minimize its free energy. So, in other words, it’s going to minimize its surface area, like a bubble! So, if I do this, this is going to give our minimum solution. Let’s do it! If I dip this in and I’ll lift it out, and if I hold this up to the camera, you can see that this is our minimum solution. And it might not be the solution you expect. This actually has length one plus root three. And that’s about 2.73. If I tell you that those roads intersect at an angle of 120 degrees, then some of you might like to try and confirm that answer. So let’s do this again! Let’s do this for three towns this time. I’ve made another prop here, for three towns, and if I dip this into my soapy water, let’s see what answer we get this time. If I hold this up to the camera, you see that I create a extra point there in the middle of the triangle. And these extra points that you create are called ‘Steiner points.’ And if you want to solve problems like this, they always look the same. They’re always three roads connected together at angles of 120 degrees. So this was our solution for three towns. Our solution for four towns looked like this, so this time, we have two Steiner points. And we can keep going. For five towns, the answer is this. And this is the answer for six Now, for eight towns, well–here’s a solution, this is the internal solution for eight towns, but it isn’t the smallest. In fact, if you connect the perimeter together, the answer is slightly smaller. So the internal solution is just a local minimum. You can think of these minimums as like valleys, and you can sit quite happily in one of those valleys, but it might not be the lowest answer. But to get to the lowest answer, you have to put in some energy first. And we can do this with our soap film Let’s try it out! If I take our four cities again– if I put this into the soapy water and I pull this out in a slightly different way, I’ve got now a different solution. It’s just a U shape like we’ve seen before. And this is one of our local minimums. And if you want to get the true answer you might have to do this a number of times and get a few of these local minimums and then you need to check which one is the true minimum. But perhaps I can do something about this, because if I take this local minimum solution and blow on it, I now get our minimum solution. This has real world application. So if you want to find the minimum length of motorways or building gas pipes, or anything like that– even if you had an obstacle that you have to build around, all you need to do is just cut out a section of your Perspex® plate there, and the soap film will go around it too. It’s very clever! And if you have been, thanks for watching.

Bernard Jenkins

100 Comments

  1. Nope. The length is (((1/2)*2)*2)+the length of the line that joins A-D line with B-C line (around one quarter)

  2. + singingbanana 120 degrees. It reminds me bees make hexagonal honeycomb with internal 120 degrees, which is with the minimum used material.

  3. Wow James! You are nailing it my friend. Nothing could be better for me than the answer given by Nature itself for the puzzle I was looking to solve. That's the sheer power of Equilibrium. Thanks for these types of puzzles!

  4. That was fantastic……have you built an 8 point prop?…. I'd like to see that

  5. So did he loose some road (bubble) when he blew on the U (local minimum) shape to get the true minimum? They seemed the same to me so how is it less material (road)? Thanks

  6. Dr. Grime, the solution for the regular hexagon (of side 1) is not that shown in the video, which has lenght 3.sqrt3, bigger than 5, if you consider the perimeter of the hexagon except for one segment.

    Excellent video!

  7. so i originally though out the cross solution, but when i heard that that wasn't the answer, i thought of the exact shape that the soapy water produced, bit i just thought that the middle line would be 0,5 miles long. now i am struggling to figure out how does the 1 + (squareroot) 3 comes from. can someone explain?

  8. i would have loved if you showed how this can actually be solved by using the lagrange formalism

  9. A soap film contained by any fixed boundary will acquire its minimum free energy when it reaches equilibrium. As the free energy of a film is proportional to its area, the area will also be minimized. Consequently soap films can be used to solve mathematical problems requiring the minimization of a surface area contained by a boundary. In order to obtain analogue solutions, we require a frame to form the boundary of the surface. When the frame is withdrawn from a bath of a soap solution a soap film will form which will attain its minimum area configuration on reaching to equilibrium.

    Joseph Plateau discovered experimentally, over a hundred years ago, that soap films contained by a framework always stratify three geometrical conditions:

    1) Three smooth surfaces of a soap film intersect along a line
    2) The angle between any two tangent planes to the intersecting surfaces, at any point along the line of intersection of three surfaces, is 120°.
    3) Four of the lines, each formed by the intersection of three surfaces, meet at a point and the angle between any pair of adjacent lines is 109° 28'

  10. Soap bubbles solve problem super computer would take 10 years to solve

  11. I love your experiment – it would be a brilliant outreach activity! 🙂

  12. I tried this myself and the hexagon solution you gave is wrong. You gave us the internal solution to the problem which is = 5.196. But if you connect the perimeter together, like you did in the octagon solution, then you get 5. Remember that you don't have to go all the way around like you showed is in your octagon picture. The towns are still connected if you just connect 1 to 2 to 3 to 4 to 5 to 6. (No need to go from 6 to 1).

  13. Maybe you could do a spinoff video about minimal spanning trees?

  14. Wow! That bubble pathway is so perfect! And that's such a clever way to find the solution! When you said the cross wasn't the most efficient way, I had a feeling it might be something halfway between the H and the cross, but I didn't quite visualize it that way! Bravo!

  15. 3:53 why would you fill the entire perimeter? you can remove one of those lines (the same way you removed one of them in the square and got a U form)

  16. Wait, here're a few guesses before I finish:

    A has a road to B (1)
    There is a diagonal from A to D (sqrt(2))
    There is a half-diagonal from C to the midpoint of AD (sqrt(2)/2)

    Does that work?

    <launches ipython>

    3.121320343559643; Nope, cross is more efficient at 2.8284271247461903

    Perhaps A to B (1)
    from the midpoint of AB to the centerpoint (0.5)
    from the midpoint to both C and D (2*1/2*sqrt(2)=sqrt(2))

    That's 2.914213562373095; cross is still better.

    Perhaps A to B then a line from the midpoint of AB to C and D?

    This is moving into weird triggy areas.

    The equation is 1+2*math.sqrt(0.5**2+1), which yields 3.23606797749979- possibly my worst guess yet.

    I would guess that it's a 'Z' shape, but that can't possibly be right- 2+sqrt(2), which is obviously greater than 3 whereas my best is the cross at 2.8<3.

    Oh well, I'm guessing it's going to be like the the 2.9 answer, but not to the midpoint.

  17. This is brilliant and you are a great teacher in each of your videos 🙂

  18. How does this work in 3D? How to connect all the vertices of a cube or other platonic solids? What would be the optimum angle?

  19. My mind is so blown.

    I was fully convinced that the X solution was it; because of the 2√2 thing.

    But nah; I should have thought in a more hexagonal way. Beehives and structural efficiency and all that.

    … Seriously though, that bubble thing is AMAZING.

  20. I got (3sqrt(3))/2 which is about 2.598. I'm probably wrong though….

  21. Hello!I am recently writing my Math Essay about the motorway problem (for general cases) for three randomly-chose points. May I take some screenshot from this video and use some of your words as evidences in my Essay? I will carefully cite everything I used from this video. Please tell me wether I may do this. Thank you very much!!☆⌒(*^-゜)v

  22. it's pretty obvious that is the minimum solution (knowing this solution already) but I was lead in the direction using only the lines that you showed (the two diagnols, and the 4 outer lines)

  23. You found the solution in the solution (get it? Soapy water… It's a solution!) I'll get me coat

  24. I love your videos James!
    I want to tell you that you've largely contributed to me deciding to learn to speak English. It started out 3 to 4 years ago when I started watching Numberphile, back then I could barely keep up with the speed at which native speakers speak. And now, I'm practically fluent. So thanks for being so passionate about what you do, it's always a pleasure to watch your videos.

  25. can someone write the calculations simply? all I see is text symbols of the shape but no method of how they gt there answer. thx

  26. I know James Grime is a fan of Johnny Ball's and I think this demonstration may have been largely inspired by him. On a BBC children's show way back, Johnny had the same pegs and soap bubble apparatus (only larger) and showed how the M1, M5 and M6 connect up in the same minimal way. (Sorry if this was already mentioned – I gave up before reading all 640+ comments :-))

  27. By far my favourite math related video I have ever seen, a very practical and elegant solution to a seemingly simple problem. When you said that 2sq{2} was not the answer, I was extremely surprised. This video gave me a new perspective on solving problems and the integration of local minimums into finding the true solution. Thank you James 🙂

  28. Damn, so cool. Problems that seem to have various solutions because local minima are always fascinating

  29. You sir, just blew my mind
    And I've seen a lot of these puzzles on YouTube but dayum , that was something truly awesome

  30. I was saddened to find that this only applies in truly Euclidean coordinate systems, and not in simplified systems like Manhattan geometry. This relies on a 120-degree angle being a certain length, which can't happen in simplified systems where a Knight's Move is actually 2 or 3 units long.

  31. So the reason why the solution of >6 towns isn't hexagonal (120°) is that in nature (e.g. honeycomb) there would always be some point within the outer ring of >6 points…?
    In other words: the hexagon dictates the position of the steiner points, of which the connecting lines are a necessary outcome.

  32. 1+ square root of 3 ~ 2.73 which is approximately 'e'

    Coincindence? Perhaps

  33. There haven't been many things i saw in my life, that amazed me so hard like watching this video.
    I would love to see that with the ,,cities" placed random (not in a square or regular triangle).

  34. Ha! My first thought was a Feynman diagram for electron interaction.

  35. What's the optimal motorway for 7? Would it be in hexagonal form or would it be (almost) the perimeter?

  36. please show the soap solution for 8 point object now man, its the logical next step after showing us all this info

  37. Now I want to see you use your perspex and soapy water to solve the regular heptagon.

  38. This is still one of the coolest videos ever haha I love how simple the solution is when you apply it to physical phenomena. It’s crazy how our world is shaped inevitably by math 🙂

  39. I also noticed that the optimal paths were seen in atomic structures and the explanation of local minimums is very familiar. Cool.

  40. Nobody's commenting on the brilliant labeling of the axis in the graph at 3:56 ?
    I audibly laughed at that

  41. 4:04 Be careful you don't end up as a recurring cutaway gag on HIGNFY.

  42. This is not a traffic solution though as it's highly condensed traffic

  43. wow ill teach this to my math students, they always ask me real life applications of math and i stumble upon finding an easy example every time

  44. Why is no one else marvelling at the fact that the universe loves regular hexagons? Bees, soapy water, and optimization problems: all the same.

  45. As much as I don't like to resort to physics to solve a math problem, if it works, it works. Brilliant.

Leave a Reply

Your email address will not be published. Required fields are marked *