Отзывы пользователей

Дан многоугольник на плоскости, невыпуклый и несамопересекающийся

Дан многоугольник на плоскости, невыпуклый и несамопересекающийся. Д – множество точек, принадлежащих тем диагоналям многоугольника, которые не вылезают за его пределы (то есть лежат либо целиком внутри, либо частью внутри, частью на контуре). Концы этих диагоналей тоже включаются в Д. Докажите, что любые две точки из Д можно соединить ломаной, целиком принадлежащей Д.


Решение

Будем доказывать по индукции более сильное утверждение, состоящее из двух частей: 1) любые две точки множества Д можно соединить ломанной, целиком принадлежащей Д; 2) любая сторона n -угольника имеет общую точку с множеством Д. При этом данный n -угольник может быть и выпуклым, n 4 . При n=4 доказательство очевидно. Пусть теперь n произвольно. Так как n 5 , то существует диагональ, целиком лежащая внутри многоугольника (известная задача на принцип крайнего). Разрежем многоугольник вдоль этой диагонали. К каждой из частей мы можем применить предположение индукции (в случае, если одна из частей – треугольник, достаточно применить предположение индукции ко второй части). Из утверждений 1) и 2) для каждой из частей легко получаются утверждения 1) и 2) для целого многоугольника.

 
Поделиться: