Problem 19 · 2024 Math Kangaroo
Stretch
Logic & Word Problems
caseworkcareful-counting
The map shows the seven subway lines of a city. The stations are shown by circles. Martin wants to colour in the subway lines on the plan. If two lines share a common station, they must have different colours. What is the smallest number of different colours he can use?
Show answer
Answer: A — 3
Show hints
Hint 1 of 3
Two lines need different colours only when they share a station, so first hunt for lines that all meet one another.
Still stuck? Show hint 2 →
Hint 2 of 3
If you can find three lines where every pair shares a station, those three already need three different colours — so you can never do it with just two.
Still stuck? Show hint 3 →
Hint 3 of 3
After that, try to colour the rest of the lines reusing only those three colours; if it works, three is the answer.
Show solution
Approach: find three lines that all meet (needs 3 colours), then colour everything with 3
- Lines that cross at a shared station must get different colours.
- On the map there are three lines that each share a station with the other two, so those three lines need three different colours — two colours can never be enough.
- Going line by line, every remaining line shares stations with only lines you have already coloured, so it can always reuse one of the three colours.
- Three colours are both needed and enough, so the smallest number is 3.
Mark:
· log in to save