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