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