Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/circles/oim/materials/vypukl.doc Дата изменения: Fri Oct 22 16:22:01 2004 Дата индексирования: Sat Dec 22 16:30:59 2007 Кодировка: koi8-r Поисковые слова: messenger

ВЫПУКЛЫЕ МНОЖЕСТВА (П. В. Семенов, школа в «Менделеево», 2004)


Множество называется выпуклым, если вместе с любыми двумя своими точками
целиком содержит отрезок, их соединяющий.
Пример 1. На числовой прямой выпуклые множества - это промежутки, и
только они.
Пример 2. Выпуклость многоугольника означает, что он лежит по одну сторону
от каждой своей стороны

Задача 1. Докажите, что:
а) круг - выпуклое множество;
б) множество точек, лежащих выше параболы [pic] выпукло;
в) пересечение выпуклых множеств выпукло;
г) выпуклость четырехугольника означает, что его диагонали пересекаются.

Задача 2.
а) На прямой есть три отрезка, любые два из которых пересекаются.
Докажите, есть точка, принадлежащая всем трем отрезкам.
б) Докажите, что в а) вместо [pic] можно поставить любое [pic].
в) На прямой есть [pic] выпуклых множеств, любые два из которых
пересекаются. Докажите, есть точка, принадлежащая всем множествам.
г) Верно ли в) для бесконечного числа выпуклых множеств?

Задача 3.
а) На плоскости есть [pic] прямоугольников со сторонами, параллельными осям
координат. Известно, что любые два прямоугольника пересекаются. Докажите,
есть точка, принадлежащая всем прямоугольникам.
б) Отрезок покрыт конечным числом меньших отрезков. Докажите, что левые
половины этих отрезков покрывают не менее половины длины всего отрезка.
в) Отрезок покрыт конечным числом меньших отрезков. Докажите, что несколько
непересекающихся отрезков по длине не меньше половины всего отрезка.
г) Квадрат [pic] разрезан на несколько прямоугольников. Докажите, что
можно закрасить несколько из них так, чтобы их проекция на одну сторону
квадрата имела длину не меньше [pic], а проекция на другую сторону квадрата
имела длину не больше [pic].

Задача 4.
а) На плоскости есть 5 точек (никакие 3 не лежат на одной прямой).
Докажите, что какие-то 4 лежат в вершинах выпуклого четырехугольника.
б) На плоскости есть 5 точек, любые 4 из которых лежат в вершинах
выпуклого четырехугольника. Докажите, что это - вершины выпуклого
пятиугольника.
в) Докажите б) для [pic]точек.
г) На плоскости задано 6 точек (никакие 3 не лежат на одной прямой).
Докажите, что из них можно выбрать 3 так, чтобы один из углов
треугольника с вершинами в этих точках был не меньше 120(;

Задача 5. (Теорема Хелли)
а) На плоскости даны четыре выпуклые фигуры, каждые три из которых имеют
общую точку. Докажите, что все эти фигуры имеют общую точку. б) То же для
[pic] выпуклых фигур.
в) Привести пример, показывающий, что а) неверно в случае невыпуклых
фигур.
г) Привести пример, показывающий, что б) неверно для бесконечного числа
замкнутых полуплоскостей.

ПРИМЕНЕНИЯ ТЕОРЕМЫ ХЕЛЛИ.
Задача 6.
а) Докажите, что внутри выпуклого семиугольника есть точка, не
принадлежащая ни одному из четырехугольников, образованных четверками его
соседних вершин.
б) Плоскость освещена несколькими прожекторами, каждый из которых освещает
некоторую полуплоскость. Докажите, что для освещения всей плоскости
достаточно некоторых трех прожекторов.
в) Резидент отравляет жизнь в круге радиуса 1 км. Известно, что, меняя
место резидентуры, он может отравить жизнь в любых трех точках плоскости из
n данных. Доказать, что он сможет отравить жизнь и сразу во всех из этих
n точек.
г) Любые две фигуры из [pic] плоских выпуклых фигур имеют общую точку.
Тогда через любую точку плоскости можно провести прямую, пересекающую все
фигуры.
д) Комната имеет форму невыпуклого многоугольника. Известно, что любые три
стены комнаты можно осветить, подходящим образом располагая люстру внутри
комнаты. Докажите, что все стены можно осветить из некоторой точки комнаты.

е) Про n вертикальных отрезков известно, что любые три из них можно
перечеркнуть какой-нибудь наклонной прямой. Докажите, что и все отрезки
сразу можно перечеркнуть какой-нибудь наклонной прямой. (Отрезки можно
заменить выпуклыми фигурами).

Задача 7 (Что-то вроде описанной окружности)
а) Стороны треугольника не больше [pic]. Докажите, что радиус описанной
окружности не больше [pic].
б) Есть [pic] кругов радиуса [pic], любые 3 из которых пересекаются.
Докажите, что все эти круги можно накрыть одним кругом радиуса 2r.
в) Попарные расстояния между [pic] точками на плоскости не больше
единицы. Докажите, что все эти точки помещаются в некотором круге радиуса
[pic] (теорема Юнга).
г) Если диаметр плоской фигуры меньше [pic], то вся фигура лежит в
некотором круге радиуса [pic].

Задача 8 (Что-то вроде центра)
а) Для любых 7 точек на плоскости можно найти точку О такую, что по обе
стороны от любой прямой, проходящей через О лежит не менее трех из этих
точек. (Прямая включается в полуплоскость.)
б) Для N точек ответ N/3. (Указание: рассмотреть полуплоскости с
границей, в которых - больше 2N/3 точек и применить теорему Хелли для
полуплоскостей.)
в) Привести пример, показывающий неулучшаемость оценки 1/3 в б).
г) Пусть О - центр тяжести треугольника и АВ - «хорда» проходящая через
О. Тогда и АО и ВО не меньше трети АВ.
д) Внутри любого многоугольника есть точка О такая, что отрезки любой
хорды, проходящей через нее, не меньше трети хорды. (Указание: для каждой
граничной точки рассмотреть (2/3)-гомотетичные образы фигуры.)
е) Внутри треугольника нет точки О такой, что отрезки любой хорды,
проходящей через нее, больше трети хорды. Значит, оценка 1/3 в д)
неулучшаема.

Задача 9. (Что-то вроде комбинаторики)
а) На круглом столе радиуса [pic] расположено без наложений [pic] монет
радиуса [pic] так, что больше ни одной монеты положить нельзя. Доказать,
что [pic].
б) В прямоугольнике 20 (25 расположено 120 единичных квадратов. Докажите,
что в него поместится не задевающий их круг единичного диаметра.
в) В круге радиуса 16 расположены 650 точек. Докажите, что есть круговое
кольцо с внутренним радиусом 2 и внешним радиусом 3, в котором лежит
не менее 10 из этих точек.
г) Докажите, что в выпуклый многоугольник площади S и периметра P можно
вписать круг радиуса S/P.