On Thursday this week Marty Ross (one of the Maths Masters!) spoke to Years 8, 9, 10 and 11 here at school to speak to students about the interesting aspects of mathematics! In their recent article for The Education Age they write about the mathematics involved in touring schools to speak – see below.
Also Marty meantioned a great site for of Geometry Games, it can be found here: http://www.geometrygames.org/
The Maths Masters’ Tour De Victoria
Burkard Polster and Marty Ross
August 31, 2009
Surprising as it might seem, mathematical speakers are sometimes in very high demand. In anticipation of things going really crazy, we have planned the Ultimate Maths Masters Tour. Our route will take in 34 of Victoria’s friendliest and prettiest towns.
The plan is to start in Melbourne and to fly the Mathscopter in straight lines from town to town. Our route will consist of one big loop, finally ending back in Melbourne. There are many loopy routes to choose from, but being Maths Masters we can only be really happy with the shortest possible one.
We are reasonably sure that the shortest tour of Victoria is that indicated in the diagram, coming to a total of 2172 kilometers. Why only reasonably sure? After all, isn’t it simply a matter of taking all possible loops and measuring which one is the shortest? Yes. And No.
Starting in Melbourne, there are 34 possible towns for our first stop. There are then 33 possibilities for the second town, then 32 and so on. This means that we have 34 x 33 x 32 x … 3 x 2 x 1 possible loops to consider. Oh, but we do get to divide by two: this monster multiplication counts each loop twice, once for each possible direction of travel. That leaves us with a mere 1.5 x 1038 loops to choose from.
This is an incredibly large number. Imagine we had a billion supercomputers working away, each analysing a trillion loops per second. Then we’d have all the loops analysed in about five billion years: probably just in time to see Victoria and the rest of the Earth plummet into the sun, making the whole calculation somewhat redundant.
So, how did we come up with our proposed route? The argument comes in two parts, beginning with a very clever idea. To illustrate, imagine starting with any loopy tour, and choose any two unconnected segments of that tour. They may be anywhere, but to begin with let’s suppose the two segments actually cross.
We now consider replacing those two segments with two different segments connecting in pairs the same four towns: there will always be such a choice of segments that also keeps the whole tour as one big loop. And, since the original segments crossed, the new segments will be uncrossed and will definitely shorten the tour.
Even if the original segments do not cross, the competing segments may shorten the tour. It’s simply a matter of trying and comparing.
With this simple idea, we now have an easy and relatively quick procedure for coming up with a candidate for the shortest tour. We first start with any loopy route, and we consider all possible pairs of unconnected segments: for our Victorian tour, a total of 560 pairs.
For each pair we then consider whether the suggested interchange shortens our tour; we choose whichever interchange shortens the most, creating a new loopy tour. Then we try to shorten again, and again, until no interchange shortens further. This final route is our candidate for shortest route overall.
This procedure does not always detect the truly shortest route. However, in practice the approach often gives strikingly good results, very quickly providing a route which is very close to the shortest.
What we have been discussing here is known as the Traveling Salesman Problem. The difficulty of this problem, of guaranteeing to have found a truly shortest route, is infamous. No one knows a watertight procedure that does not take an astronomically long time. So, much work is devoted to “reasonably sure” procedures of the type we have described.
Very annoying! Mathematicians hate to say “near enough is good enough”.
But, when the alternative is to wait billions of years for the answer, sometimes even mathematicians are willing to bite their tongues.
This year 5 students, Bec W, Hannah M, Jayk B, Maria T, Tara P set of to complete against teams from all over Melbourne in Melb Uni’s Schools Maths Olympics. The team had to try and answer as many problem solving questions as they could within 1 hour. Although the students didn’t win they did have heaps of fun and vowed to return next year. More info about the comp can be found on the MUMS website: http://www.ms.unimelb.edu.au/~mums/olympics/smo.html
No Comments » | 
Interesting, numbers, puzzle | Tagged: Maths, Melbourne, Olympics, Schools, University | 
Permalink
Posted by yousmags
