Условие
Картинная галерея представляет собой невыпуклый
n-угольник. Докажите, что для обзора всей галереи достаточно
[
n/3] сторожей.
Решение
Разрежем данный
n-угольник непересекающимися диагоналями на треугольники
(см. задачу
22.22). Вершины
n-угольника можно раскрасить в три цвета
так, что все вершины каждого из полученных треугольников будут разного
цвета (см. задачу
23.40). Вершин какого-нибудь цвета будет не более
[
n/3]; сторожей достаточно поставить в этих вершинах.
Источники и прецеденты использования
