Задача 15.
Маша хочет раскрасить кружки на картинке так, чтобы любые два кружка, соединённые линией, были раскрашены в разные цвета. Какое наименьшее количество цветов ей нужно?
(А) 2
(Б) 3
(В) 4
(Г) 5
(Д) 6
Ответ на Задачу 15.
Ответ: Б
Решение:
Обозначим кружки буквами для простоты описания решения. Начнём с круга D, так как он соединён с максимальным количеством других кружков. Закрасим его в один цвет (на рисунке это синий). Затем переходим к кружку А, его закрасим в другой цвет (на рисунке это красный). Следующий кружок С. Он соприкасается с А и D, поэтому его необходимо раскрасить в третий цвет (зелёный). Кружок F соприкасается с С и D, но не соприкасается с А, значит его можно раскрасить тем же цветом, что и А. Аналогично подбираем цвета для G, E и B. И видим, что достаточно трёх разных цветов.
