Условие
На острове все страны треугольной формы (границы прямые). Если две страны граничат, то по целой стороне. Докажите, что страны можно раскрасить в 3 цвета так, что соседние по стороне страны будут покрашены в разные цвета.
Решение
Предположим, что некоторые острова, удовлетворяющие условию задачи, невозможно
покрасить в три цвета так, чтобы каждая страна была покрашена в свой
цвет, а соседние страны были покрашены в разные цвета. Выберем
из них остров, на котором число стран самое маленькое. Рассмотрим
какую–нибудь прибрежную страну (то есть какую–нибудь страну,
одной из сторон выходящую на берег). В силу выбора, весь
остальной остров можно покрасить в три цвета. Но рассматриваемая
страна граничит только с двумя странами, а значит, для неё запрещены
только два цвета. Поэтому её тоже можно покрасить. Получили противоречие.
Следовательно, карту любого острова, удовлетворяющего условию задачи, можно
раскрасить в три цвета так, чтобы выполнялись требования задачи.
Источники и прецеденты использования
