Archive | October, 2013

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

23. The Big Freeze Problem

24 Oct
maths with zombies

…because everything’s better with zombies!

The zombie apocalypse has begun and a large group of you have sought refuge in the far North because you’ve heard that zombies can’t move at low temperatures. This is because they seize up if they get too cold. However, at the northern latitudes where you’re hiding out, it’s not always sufficiently cold for this to happen, and for three months of the year (June, July and August) the temperatures are warm enough for the zombie to advance. This is quickly becoming known as the walking season and is dreaded by everyone since it’s when almost all zombie attacks take place. Only 30% of the zombies survive their annual chill, and in each month when it’s warm enough for them to move, they can stagger 100 miles. It’s now the end of August and the temperatures have just started to drop so the zombies have frozen up for the winter meaning this year’s walking season is over. You’ve estimated that 2 million zombies crossed the Canadian border, heading north, just before this happened. How long will it take for this zombie horde to reach you 1,300 miles to the North and how many will be left when they do?

A: It will take four years for them to reach us, and there will be 16,200 zombies left when they do.

B: They’ll reach us in four years and ten months, and there will only be 4,860 left by then.

C: It will take the zombies five years and ten months to get here, and there will be 1,458 left.

D: All the zombies will die from the cold before they reach here so we’re completely safe.

Scroll down to see the right answer…









What answer did you get?

A: You’re almost right, but the zombies will still be 100 miles away after four years and they will have to survive another winter before they can cover these last few miles. This will thin out their numbers even more meaning there will be many fewer for you to worry about.

B: Spot on! Now you know when the zombies will arrive and how many there will be, you can start preparing for their arrival.

C: I don’t know what went wrong there, but you’re a few months out, and there will be many more zombies than you’re expecting. This means you’ll be caught unaware and unprepared when they finally turn up on your door step.

D: I don’t know what went wrong there, but you’re a few months out, and there will be many more zombies than you’re expecting. This means you’ll be caught unaware and unprepared when they finally turn up on your door step.

How to work it out: At the start of this problem, the 2 million zombies are frozen in place 1,300 miles to your south. This means they won’t be able to start moving until the temperatures warm again next June. During this time, only 30% (or 0.3, if we express this as a decimal fraction) will survive. To work out how many this is, multiply the initial number (2 million) by the percentage expressed as a decimal fraction (0.3). This calculation tells you that at the start of the next summer there will only be 600,000 zombies left. Over the next three months, they’ll stagger 100 miles each month, or 300 miles in total. So, in exactly one year’s time, when the zombies freeze up again, there will be a horde of 600,000 zombies 1,000 miles away (the initial 1,300 minus the 300 they’ve been able to move in the summer months). If you repeat these calculations for the next year, starting with these new values, you’ll find that at the end of the second year, the zombies will be 700 miles away and there will be 180,000 of them. At the end of the third year, there will be just 54,000 left and they’ll be 400 miles away. At the end of the fourth year, they’ll be only 100 miles away, but their numbers will have been whittled down to 16,200. During the next winter, 70% of these zombies will die, meaning there will only be 4,860 still alive to start walking nine months later at the beginning of the following June. Since they can cover 100 miles per month, this means these remaining zombies will reach you at the start of July. So in total, you’ve got four years and ten months to work out a way for you to be able to kill almost 5,000 zombies before any of them get you. Got any ideas?

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.

22. The Recruitment Problem

10 Oct
maths with zombies

…because everything’s better with zombies!

There’s a zombie outbreak in a city of 15 million people and the army has been ordered to deal with it, and as the general that means you have to decide what to do. You could send in all your troops, but then you would have none spare if there’s another outbreak somewhere else. Instead, you decide to send in a skeleton force of just 1,600 soldiers with orders to recruit members of the public to help them fight the zombies. It’s a novel solution, and leaves you with plenty of men in case there are any other outbreaks, but no one else thinks it’ll work. To prove them wrong, you set out to do the maths. You know that each soldier can hunt down and kill twenty zombies a day. In the evening, each soldier can also recruit one new soldier from the people in the city who will join the fight the following day. However, each night the zombies will fight back and infect five normal people who then become zombies. You know there’s currently 50,000 zombies in the city. Have you made the right decision?

A: Yes, the maths shows this is the right decision. It might take a while, but the strategy will work and the soldiers will regain control of the city.

B: The maths shows that while the strategy is sound, you’d need to send in more troops at the start for it to be successfully implemented.

c: No. The maths shows that this is the wrong decision. No matter how many soldiers you sent in, the strategy will never work. This is because the number of zombies keeps increasing at a rate faster than the soldiers can kill them. The only thing which can stop the outbreak spreading is to nuke the entire city before the situation gets any worse.

Scroll down to see the right answer…









What answer did you get?

A: Your maths must have been wrong. If you send in only 1,600 soldiers, you’ll never managed to get the outbreak under control and the city will be lost within days.
B: Spot on! Just as well you did the maths, or you would have sent in too few troops. In fact, while an initial force of 1,600 men cannot get the outbreak under control by following your strategy, sending in just 67 more in your initial force would ensure it worked.
C: Whoa, I don’t know what happened with your calculations there, but you’re way off. Nuking the city will certainly get the outbreak under control, but it’ll also needlessly kill a lot of innocent people. Maybe you should check your figures before you take quite such a drastic decision.

How to work it out: The maths here is quite complicated, but it reveals something very interesting. To work out the number of zombies at the start of each day, you need to know how many zombies and soldiers there were at the start of the day before. If you know this, you can use the formula Nt+1 = (Nt – (St * 20))*5 to calculate the number of zombies on at the start of any given day. In this formula, St is the number of soldiers at the start of the day before while Nt is the number of zombie at the start of the preceding day. Nt+1 is the number of zombies there will be at the start of the day itself. The value of 20 is the number of zombies which each soldier will kill during each day, while 5 is the number of people which each zombie will infect each night. Using this formula, you can work out what effect sending in different numbers of troops will have. Start by calculating the number of zombies at the start of day two of the campaign (remembering that the number of soldiers will double each day because of the new recruits) and then repeat this for days 3 to 10. If the number of zombies at the start of a day ever becomes zero, then the zombie outbreak will have been extinguished. If it doesn’t, it hasn’t.

If you plug in the initial number of soldiers (1,600) and zombies (50,000) into this formula, you’ll see that the number of zombies quickly spirals out of control, reaching a whopping 17,088,000 by the start of day six, or more than the entire population of the city. This might make it seem like this strategy would never work, but this isn’t true. For example, if you start in 1,700 soldiers and repeat the calculations, you’ll see that the zombie problem gets sorted in just four days. In fact, the difference between success and failure comes down to just one single soldier. If you send in 1,666 soldiers, the city will be over-run by zombies by the start of day nine of your campaign. In contrast, if you send in 1,667 soldiers, the last zombie will be killed on day eight. This means the 1,667th soldier is an example of what Malcolm Gadwell calls a tipping point, where small changes can have big impacts on the final outcome of certain events. It is also an example of a chaotic system where small changes in the starting values can result in very different outcomes further down the road. You can see this in the graph below which shows how the number of zombies changes over time under the four scenarios discussed above.

As shown in this graph, the recruitment problem is a chaotic system, with very different outcomes arising from very similar starting points. In this case, just one soldier makes all the difference between success and failure.

As shown in this graph, the recruitment problem is a chaotic system, with very different outcomes arising from very similar starting points. In this case, just one soldier makes all the difference between success and failure.



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.