|
|
 |
Условие
Вершины выпуклого многоугольника раскрашены в три цвета так, что каждый цвет присутствует и никакие две соседние вершины не окрашены в один цвет. Докажите, что многоугольник можно разбить диагоналями на треугольники так, чтобы у каждого треугольника вершины были трёх разных цветов.
Подсказка
Используйте индукцию по числу вершин многоугольника.
Решение
Обозначим цвета цифрами 1, 2, 3. Доказательство проведём индукцией по числу n вершин многоугольника. База (n = 3) тривиальна.
Шаг индукции. Пусть n > 3. Выберем две вершины A и B одного цвета, пусть это цвет 1. Точки A и B делят контур многоугольника на две ломаные. На каждой из этих ломаных есть вершина цвета, отличного от 1. Заметим, что можно найти такие две точки C и D цветов 2 и 3, что C и D лежат на разных ломаных. Действительно, это легко сделать, если на каждой из двух ломаных присутствуют вершины как цвета 2, так и цвета 3. Если же на одной ломаной нет вершин, скажем, цвета 2, то на этой ломаной все вершины цвета 3, и значит, на другой ломаной найдётся вершина цвета 2. Разобьём наш n-угольник на два многоугольника M1, M2 диагональю CD. Каждый из этих многоугольников удовлетворяет условию задачи. По предположению индукции каждый из них разбить на треугольники, у которых вершины окрашены в разные цвета. Это и даст разбиение исходного многоугольника.
Источники и прецеденты использования
| web-сайт | |
| задача |
