Задача
Проведём в выпуклом многоугольнике некоторые диагонали так, что никакие две из них не пересекаются (из одной вершины могут выходить несколько диагоналей). Доказать, что найдутся по крайней мере две вершины многоугольника, из которых не проведено ни одной диагонали.
Решение
Пустьn— число вершин многоугольника. Докажем индукцией поn, что найдутся по крайней мере две несмежные вершины, из которых не проведено ни одной диагонали. Приn= 4 это очевидно. Докажем шаг индукции. Пусть в многоугольнике проведена диагональ через вершиныMиN. Эта диагональ разрезает его на два многоугольника с меньшим числом вершин, в каждом из которых по предположению индукции найдутся две несмежные вершины, из которых не проведены диагонали. Ясно, что для каждого многоугольника одна из этих вершин отлична отMиN(если отрезан треугольник, то нужная вершина — отличная отMиN).
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь