Timetabling by colouring
Tonight's idea
Six exams need a timetable. Two exams that share a student cannot sit in the same slot. What is the smallest number of slots?
Draw it. Make a dot for each exam and join two dots when some student takes both. The picture is a graph: dots and links, where only the connections matter. Now give each dot a colour so that joined dots never match. Each colour is a slot, so the fewest colours is the fewest slots.
To be sure a number is the fewest, you need two arguments.
A colouring that uses \(k\) colours proves \(k\) are enough. A reason why \(k - 1\) must fail proves \(k\) are needed.
The handiest reason is a triangle. Three dots all joined to each other need three different colours.
Colouring a map is the same problem: countries are dots, and a shared border is a link. You met that in Four colours are always enough.
Watch one: six exams
Needed. Math, Physics and Chemistry form a triangle, so two slots cannot work.
Enough. Give that triangle slots 1, 2, 3. History is joined to Physics and Chemistry, so it takes slot 1. Art is joined to History: slot 2. French is joined to Art and Math: slot 3. Every link now joins two different numbers.
Three are needed and three are enough, so the answer is exactly 3.
Colour maps by clicking, with neighbours never matching: mathdetours.com/demos/colour.html. Greedy auto uses the rule in question 3. The Odd wheel map is question 4 with one more region round the outside.
Your turn
- Ana takes Biology, Geography and Music. Ben takes Biology, Music and Drama. Cal takes Drama and Spanish. Draw the graph of the five exams. Find the fewest slots, with a reason, and write out a timetable.
- Five exams clash in a ring, as in the figure. There is no triangle. (a) Go round the ring and show that two colours fail. (b) Colour it with three.
- The greedy rule: take the dots in some order and give each the lowest-numbered slot not used by a dot it is joined to. Use it on the row A, B, C, D in the figure. (a) Take the order A, D, B, C. How many slots? (b) Find an order that uses two. (c) What does this say about greedy?
- (a) Add a centre joined to all five dots of the ring. How many colours now? Give both arguments. (b) Change the ring to six dots, with a centre joined to all six. How many?
Stretch: a promise for any school
In a large school no exam clashes with more than three others. Explain why four slots are always enough, however many exams there are. Use the greedy rule, and count the slots that are barred when it reaches an exam.
Answers
- Links: Biology–Geography, Biology–Music, Geography–Music (Ana); Biology–Drama, Music–Drama (Ben); Drama–Spanish (Cal). Biology, Geography and Music form a triangle, so three slots are needed. Three are enough: slot 1 Biology and Spanish, slot 2 Geography and Drama, slot 3 Music. Other timetables work too.
- (a) With two colours they must alternate round the ring: 1, 2, 1, 2. The fifth dot is joined to the fourth (colour 2) and the first (colour 1), so neither colour is free. (b) 1, 2, 1, 2, 3. A ring with an odd number of dots always needs three.
- (a) A gets 1. D is not joined to A, so it gets 1. B is joined to A: 2. C is joined to B (2) and D (1): 3. Three slots. (b) A, B, C, D gives 1, 2, 1, 2. (c) Greedy always gives a timetable with no clashes, but the number of slots depends on the order. It can use more than the fewest.
- (a) Four. Needed: the ring alone needs three, and the centre is joined to every ring dot, so it cannot reuse any of them. Enough: ring 1, 2, 1, 2, 3 and centre 4. (b) Three. A ring of six alternates 1, 2, 1, 2, 1, 2 and the centre takes 3. Two fail because the centre and any two neighbouring ring dots form a triangle.
Stretch. Run greedy in any order. When it reaches an exam, at most three of the exams it clashes with already have slots, so at most three of the slots 1, 2, 3, 4 are barred. One is always free, and greedy never needs a fifth. In general, if no dot has more than \(d\) links, \(d + 1\) colours are enough.