THE FOUR COLOUR MAP PROBLEM --------------------------- PART 1 ------ OF -- `COLOURFUL MATHEMATICS' --------------------- This is an educational mathematical game for curious people of all ages. The idea is very simple: draw a map or any picture as complicated as you wish and colour each region using the fewest possible number of colours, the only requirement being that regions sharing a common border must receive different colours. There is an analogy with standard maps where neighbouring countries receive different colours. But a quite amazing fact is that four colours will always suffice. This was verified or proved, as we say in mathematics, by K. Appel and W. Haken in 1976 making substantial use of the computer to classify thousands of configurations. An interesting account of their story is available in the popular science magazine "Scientific American", October 1977. The goal is not for kids to prove this fact, but rather to experience the problem, to draw maps and devise methods to colour them with the fewest possible number of colours. Sometimes two colours will suffice and sometimes three, but more often four is necessary. Older kids will be able to verify that three colours is in general not enough to colour their map. Using only four colours is however not as straightforward as it appears so we have provided a few more colours which should make it relatively easy for everyone to colour their maps correctly, at least with six colours. The more adventurous will reduce this number to five, or even better to four. We have included 24 maps divided in four pages: the first consists of 6 pictures for warm-ups or for younger kids, the second page contains more abstract mathematical patterns, the third consists of "traditional" maps such as Canada, USA, Europe, Africa, South America and Asia, and finally the last page contains quite challenging maps. But to really have a true feeling for the problem, you must experience by drawing your own map and several drawing tools are provided for that purpose. The computer will let you know if you coloured two neighbouring regions with the same colour, or when the map is completed by counting the number of colours you have used. This process of experiencing a problem and understanding its difficulties is, we believe, at the root of mathematical and scientific reasoning. The goal of this software is to help develop this skill. Hardware requirement: -------------------- A colour monitor is required as this is a colouring program; for technical reasons, an EGA/VGA monitor is actually necessary. A mouse is also essential; once the program is started, the mouse (with the left button) is used through "clicking" command boxes, drawing and colouring. The keyboard is used in the MAPS/SAVE menu to type a title for your maps if you wish one. The computer will check your map after each colouring; this will take correspondingly longer depending on the size of the region just coloured. The computer also verifies if the map is completed and counts the number of colours used. Installation: ------------- Insert the disk in drive A: and type A:INSTALL; the program will install itself on your hard drive C. To start the game, type "DEMOCLR". You can also run the program from a floppy but this will be much slower as the computer must sometimes read some data. The Commands: ------------- INFO: A quick explanation of the game and other commands. DRAW: The mode "NEW" will clear the drawing board to draw a new map. Drawing tools will appear to help you draw a map; there is free drawing, lines, triangles, rectangles and circles. The mode "EDIT" will let you add drawing to your map, but only on a white background to avoid creating neighbouring regions of the same colour. PAINT: In the mode "COLOURS", you have 6 colours available to colour your map; they are selected by clicking the can of your choice. The mode "WHITE" lets you erase the colours on your map for editing or recolouring. UNDO: You can remove the last drawing performed, or the last paint while colouring. MAPS: A set of 6 sample maps are available for each of the four pages, and you can save one map for each one provided for a total of 48. You can thus save completed maps or just work in progress. SAVE: You can save 6 maps on each page, using the keyboard to type a title if you wish. QUIT: Quit the game. `Colourful Mathematics': ------------------------ This is a series of educational mathematical games dealing with serious mathematical concepts. It took over a hundred years for mathematicians to prove that four colours were sufficient to colour any map in such a way that neighbouring regions receive diferent colours. This is the topic of the first game, `The Four Colour Map Problem'; you can use maps provided or draw your own, and try to use the fewest possible number of colours. Think of methods and tricks to save colours; it is in general not easy at all to use only four colours but the point is that there must be a way to do it. Sometimes you will notice that three colours is enough but more often four is necessary. The second game deals with the more general concept of graph and its chromatic number. A graph consists of circles, which we call vertices, some of them joined by lines, which we call edges. Now you must colour the vertices in such a way that two vertices joined by an edge receive different colours. The smallest possible number of colours that can be used for a graph is called the chromatic number of the graph. The goal of this game, apropriately called `The Chromatic Number of Graphs', is to get a close as possible to this number. This is a very difficult problem in general and is related to many important problems in computer science and industries. There is a simple algorithm programmed in the game and the computer will tell you, first if you make a mistake, but also if it can do better than you. To tie the computer is a great achievement and it is even possible to beat it. Indeed, there are no perfect algorithm to compute this chromatic number that uses a reasonable amount of time. Have fun! The third game introduces another important property of graphs, that of a dominating set. Starting with any graph, you have one colour to select some of the vertices so that each vertex is either coloured or is connected to a coloured one, this is what is called a dominating set. The goal is to achieve this using the smallest number of coloured vertices, or if you prefer you must find a dominating set with the fewest possible number of vertices. This problem is again very difficult even for today's computers and in some sense has the same degree of difficulty as the previous problem. The basic idea is as follows: if you were in charge of a telephone company, you would not really want to install telephone booths at every street corner because of the cost involved, but you would rather have just enough so that people could walk to one say in a reasonable amount of time. These prime locations would then roughly form a dominating set; and the smaller that set the more economical it will be for the company. Authors: -------- Comments and suggestions are most welcomed! Please write to: Claude Laflamme 5904 Silver Ridge Dr. N.W. Calgary, Alberta Canada T3B 3R9 or use electronic mail to: laflamme@acs.ucalgary.ca