Разделы 
Дополнительно
Задача по математике - 242
2014-06-07 
Вершины выпуклого многоугольника с нечетным числом сторон окрашены так, что любые две соседние вершины имеют разный цвет. Доказать, что для всякой раскраски, удовлетворяющей этому условию, многоугольник можно разбить непересекающимися диагоналями на треугольники так, чтобы концы каждой диагонали имели разный цвет.
Решение:
Доказательство проведем индукцией по числу $n$ сторон многоугольника. При $n = 3$ утверждение верно, ибо треугольник не имеет диагоналей. Пусть оно уже доказано для некоторого нечетного значения $n \geq 3$ и дан выпуклый (n+2)-угольник, вершины которого окрашены указанным в задаче способом. Тогда найдется такая вершина А, что две соседние с ней вершины имеют разный цвет. Действительно, в противном случае любые две вершины, расположенные через одну, имели бы одинаковый цвет, а в силу нечетности числа n+2 все вершины оказались бы одного цвета, что противоречило бы условию задачи. Тогда диагональ, соединяющая две вершины, соседние с вершиной А, делит (n + 2)-угольник на треугольник и (n + 1)-угольник. Если в этом (n + 1)-угольнике также найдется вершина, соседние с которой имеют разный цвет, то соединим эти две разноцветные вершины диагональю, после чего образуется еще один треугольник и n-угольник, для которого, по предположению индукции, существует требуемое разбиение. Если же такой вершины в (n + 1)-угольнике нет, то любые его вершины, расположенные через одну, имеют одинаковый цвет, т. е. все его вершины раскрашены в два цвета в чередующемся порядке. Поскольку цвет вершины А отличен от цветов соседних с ней вершин, то он отличен от цветов и всех остальных вершин исходного (n+2)-угольника. Следовательно, если с самого начала из точки А провести все выходящие из нее диагонали (n+2)-угольника, то получится требуемое разбиение. Таким образом, утверждение доказано и для следующего за числом n нечетного значения n+2.
Вершины выпуклого многоугольника с нечетным числом сторон окрашены так, что любые две соседние вершины имеют разный цвет. Доказать, что для всякой раскраски, удовлетворяющей этому условию, многоугольник можно разбить непересекающимися диагоналями на треугольники так, чтобы концы каждой диагонали имели разный цвет.
Решение:
Доказательство проведем индукцией по числу $n$ сторон многоугольника. При $n = 3$ утверждение верно, ибо треугольник не имеет диагоналей. Пусть оно уже доказано для некоторого нечетного значения $n \geq 3$ и дан выпуклый (n+2)-угольник, вершины которого окрашены указанным в задаче способом. Тогда найдется такая вершина А, что две соседние с ней вершины имеют разный цвет. Действительно, в противном случае любые две вершины, расположенные через одну, имели бы одинаковый цвет, а в силу нечетности числа n+2 все вершины оказались бы одного цвета, что противоречило бы условию задачи. Тогда диагональ, соединяющая две вершины, соседние с вершиной А, делит (n + 2)-угольник на треугольник и (n + 1)-угольник. Если в этом (n + 1)-угольнике также найдется вершина, соседние с которой имеют разный цвет, то соединим эти две разноцветные вершины диагональю, после чего образуется еще один треугольник и n-угольник, для которого, по предположению индукции, существует требуемое разбиение. Если же такой вершины в (n + 1)-угольнике нет, то любые его вершины, расположенные через одну, имеют одинаковый цвет, т. е. все его вершины раскрашены в два цвета в чередующемся порядке. Поскольку цвет вершины А отличен от цветов соседних с ней вершин, то он отличен от цветов и всех остальных вершин исходного (n+2)-угольника. Следовательно, если с самого начала из точки А провести все выходящие из нее диагонали (n+2)-угольника, то получится требуемое разбиение. Таким образом, утверждение доказано и для следующего за числом n нечетного значения n+2.
