Задача 23.
На схеме показаны семь маршрутов поездов. Кружочками обозначены станции. Миша хочет раскрасить эту схему таким образом, чтобы маршруты, имеющие общую станцию, были обозначены разными цветами. Какое наименьшее количество цветов он может использовать?
(А) 3
(Б) 4
(В) 5
(Г) 6
(Д) 7
Ответ на Задачу 23.
Ответ: А
Решение:
Линия 4 пересекается с линиями 1, 2 и 3. При этом линии 1 и 3 между собой не пересекаются, значит они могут быть раскрашены одним цветом. Линии 2 и 1 пересекаются тоже, поэтому линии 2 и 4 мы нужно раскрасить двумя другими цветами. На данный момент мы уже использовали три цвета. Линии 5 и 6 не пересекаются с линией 4, поэтому они могут быть раскрашены тем же цветом, что и линия 4. Остается линия 7. Она не пересекается с линией 2, поэтому может быть раскрашена там же цветом, что и линия 2. Таким образом, трёх цветов достаточно, чтобы раскрасить эту схему. Для наглядности см. рисунок.
