Задача
Выпуклый фанерный многоугольник P лежит на деревянном столе. В стол можно вбивать гвозди, которые не должны проходить через P, но могут касаться его границы. Фиксирующим называется набор гвоздей, не позволяющий двигать P по столу. Найдите минимальное количество гвоздей, позволяющее зафиксировать любой выпуклый многоугольник.
Решение
Если P – параллелограмм, то нужно не менее четырёх гвоздей. Действительно, если некоторая его сторона не касается никакого гвоздя, то P можно двигать в направлении двух смежных с ней сторон.
Покажем, что любой выпуклый многоугольник P можно зафиксировать четырьмя гвоздями.
Пусть окружность Ω с центром O – наибольшая из окружностей, лежащих внутри P, A1, A2, ..., Ak – точки касания Ω со сторонами P, H – выпуклая оболочка этих точек.
Предположим, что существуют такие две вершины U и V многоугольника H, что UV – диаметр Ω (рис. слева). Вобьём два гвоздя в точки U и V. Очевидно, что стороны P, содержащие U и V, параллельны, следовательно, P можно двигать только в направлении, перпендикулярном UV. Чтобы зафиксировать P, достаточно вбить еще два гвоздя, препятствующие его движению влево и вправо от прямой UV.

Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь