24. The Six Bridges Problem

31 Oct
maths with zombies

…because everything’s better with zombies!

You’re holidaying on a small archipelago of islands when a zombie outbreak catches you unaware. You manage to get to a safe house, but there’s no supplies of any kind and this means you’ll need to go on a supply run. You look at a map (see below) of the five islands in the archipelago and see that they’re connected by six bridges. Your safe house is on the northern-most island and you can see that there’s a warehouse where you can get food and drink from on the large island to the southwest. There’s a hospital where you’ll be able to get medical supplies on another large island to the southeast. Between these two large islands are a couple of small ones, one of which has a gun store on it, where you will be able to get weapons, while the other has an ammunition dump on it where you can get plenty of ammunition. You look out the window and see the zombies shambling around. They look slow and you know you’d probably be able to out-run them, but the moment they know you’re there, they’ll start following you. This means that once you cross a bridge, they’ll follow you onto it and you won’t be able to cross it again because there will be too many zombies on it. Is there a route, starting from your safe house, which will allow you to visit all the places you want to go for supplies and make it back to your safe house without having to use any of the bridges twice?

A: Yes, there’s a route which allows me to visit all the places need to go to get supplies and still get back to the safe house without having to use any of the bridges twice. I’m setting off now before things get any worse.

B: There’s no route which will allow me to visit everywhere I need to go and still get back to the safe house without having to cross the same bridge twice. The most places I can visit is three out of the four, so I’ll need to decide which one to leave out on my supply run.

The_Bridge_Problem

Scroll down to see the right answer…









A: You’re wrong, there’s no route which will allow you to visit all four places and make it back to the safe house without having to use one of the bridges twice. If you set out and try to do it, you’ll end up in big trouble!

B: You’re right, there’s no route which will allow you to get to all four locations without crossing a bridge twice. The only decision left now is which place to leave out.

How to work it out: There’s two ways to solve this problem. One is trial and error, where you try every single possible route, but that will take time, and in a zombie apocalypse speed is of the essence if you want to survive. The other is to think about it from a mathematical perspective. Each island has one place you want to visit on it. This means that you’ll need to be able to reach each island once and leave it once (otherwise you can’t get back to where you started). If you ever go onto an island and can’t leave it by a bridge you haven’t already used, you’ll be stuck. Because you have to cross every bridge on the map at least once to visit all the places you need to go, this means that if any island is connected to other islands by an odd number of bridges, you’ll end up getting stuck on it at some point. So to work out whether it is ever possible to visit every island without to using any bridge twice, all you need to do is see whether any islands are connected by an odd number of bridges. In this case, there’s two of them, the big ones to the southeast and the southwest, so if you know your maths, you can know instantly that there’s no safe route which will allow you to visit everywhere and still get back to the safe house without crossing a zombie-infested bridge, and that wouldn’t be a very good idea.

If you want to explore this problem further, you can try adding another bridge and see how this changes the outcome. If you do this, you’ll see that no matter which pair of islands you connect with a new bridge, you can manage to get round all four intended destinations and back to your safe house without having to cross any bridge twice. Why does this make a difference? It’s because this means you no longer need to use every bridge to complete your trip so the rule about needing an even number of bridges attached to each island no longer applies.

If you dig into this even deeper, you’ll see that with any number of bridges of seven and above, as long as each island has at least two bridges connecting it to other islands (i.e. so there’s no dead ends), you can complete your intended circuit safely, while any number of bridges of five of fewer, there will be at least one island only connected to another by a single bridge, meaning you can’t do it. Six is the only number of bridges which allows you to have no dead ends, but still not be able to complete your supply run successfully, and this only works with some placements of bridges and not others. For example, if the upper small island was connected to the big island to its north as its second bridge rather than the one to the southwest, you’d be able to complete the journey successfully. Again, this is because you no longer have to use all the bridges.

For those who are interested, this problem is based on a rather old puzzle called the Königsberg Bridge problem. If you want to find out more about this original problem, click here. This was the first mathematical problem every solved with graph theory, and its original solution by Euler laid the foundations for topology. This makes the Königsberg Bridge problem an important landmark in the history of mathematics.

While the problems provided here are copyright of Maths With Zombies, if you are a teacher, you can use any of these problems for free in your classes – but please credit Maths With Zombies as the original source (e.g. Downloaded from MathsWithZombies.wordpress.com). You can download a PDF handout of this problem from here.

If you do use this problem in a class, please post a comment here to let me know how you used it and how it was received by your students. These problems cannot be used for any commercial purpose without express written permission.

*****************************************************************************
From the author of For Those In Peril On The Sea, a tale of post-apocalyptic survival in a world where zombie-like infected rule the land and all the last few human survivors can do is stay on their boats and try to survive. Now available in print and as a Kindle ebook. Click here or visit www.forthoseinperil.net to find out more. To download a preview of the first three chapters, click here.

To read the Foreword Clarion Review of For Those In Peril On The Sea (where it scored five stars out of five) click here.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s