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