You are the general in charge of an army division which has been assigned the task of clearing an island of zombies. To make the job easier, you’ve divided it into 21 zones and assigned one unit of soldiers to clear each zone. The plans are all in place and the soldier are raring to go. Before you give the order, you check everything over one last time. That’s when you realise there’s as a problem: where one zone meets another, there’s a risk of soldiers from different units getting mixed up if they run into each other, especially it’s during a battle with a zombie horde. This could leave some of the units dangerously under-manned and unable to continue with their assignment until they get their missing men back. This means such confusion will slow the whole mission down, and could even result in its failure. What you need, you realise, is an easy way for the soldiers to tell which men are in which units.
Suddenly, the solution comes to you: since zombies only react to sound and movement rather than colour so there’s really no need for camouflage. This means you can simply provide brightly coloured hats to each unit, and make sure that units assigned to neighbouring zones are given different coloured hats. However, the more different coloured hats you need to order the longer it will take to start the mission, and the more zombies there will be when the fighting starts, making it more dangerous and difficult, so speed is of the essence. Given the zones you have created, what’s the minimum number of different colours of hat would you need so that the soldiers in every zone can be assigned a colour of hat that’s different from those being used in all neighbouring zones?
A: 2.
B: 3.
C: 4.
D: 5.
The Map Of The Island Showing The 21 Zones (Marked In Red):
Scroll down to see the right answer…
What answer did you get?
A: Whoa, that’s not nearly enough different colours, there will be confusion all over the place and your poor choice has put the whole mission in danger.
B: Three colours will work for most of the zones, but there will still be the potential for confusion in the area around zone 17 because two neighbouring zone will have to contain soldiers with hats of the same colour. This probably won’t endanger the whole mission, but it might slow things down.
C: Spot on. With four different colours of hats you can assign every unit a hat colour that will be different from the ones worn in every neighbouring zone.
D: That’s too many, and you’ll have wasted precious time getting hats in a colour that you don’t need. Let’s hope the zombies haven’t multiplied in this time to levels that your men can’t handle.
How to work it out: The key to solving this problem is to use something called ‘Minimal Criminals’. For this problem, a minimal criminal is the smallest example of a group of zones which shows that you cannot use a given number of colours to successfully assign different hat colours to all neighbouring zones. If you find even one of these minimal criminals on your map for a given number of colours then you cannot successfully assign the coloured hats to each zone.
Here’s an example of a minimal criminal which shows that you cannot use just two colour of hats. If you assign the red to zone 2, and yellow to zone 1, then you’d have to use a third colour for zone 4 since it touches both of these zones. There’s lots of these minimal criminals on this map.
A minimal criminal which shows that you cannot use just three colours is harder to find, but there is one, and it’s shaded in grey on the map below. This consists of a central zone surrounded by seven other zones. Each of these surrounding zones touches the central zone so they must have different colours to it. If the zones surrounding it are then assigned alternating colours, you then come to a situation with the final zone because it touches the central zone and zones with each of the two other colours. This means it has to be given a fourth colour.
Since there’s no minimal criminals which mean you can’t use four colours, you know that four different coloured hats will be enough. In fact, it’s impossible to divide the island up into zones which would require more than four colours, and this is true of any map. This is known as the four colour theorem, and while it was proposed many years ago, it was not proven until 1976 and was the first mathematical theorem which was solved using a computer.
If you want to find out more about the four colour theorem (including the rules for creating the maps and deciding which zones are considered neighbours), click here.
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.