Каталог по темам

Задачи

Страница: << 2 3 4 5 6 7 8 >> [Всего задач: 60]

Задача 78821

Темы:	[	Выпуклая оболочка и опорные прямые (плоскости)	]
	[	Выпуклые многоугольники	]
	[	ГМТ с ненулевой площадью	]
	[	Невыпуклые многоугольники	]

Сложность: 5+
Классы: 8,9,10,11

Автор: Бернштейн И.Д.

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

Решение

Итак, имеется несамопересекающийся невыпуклый n-угольник P. Рассмотрим множество T его внутренних точек, из которых видны все вершины P. Докажем, что T — выпуклый многоугольник, число сторон которого не больше n.

Каждой стороне AB многоугольника P поставим в соответствие полуплоскость, граница которой есть прямая AB (из двух таких полуплоскостей мы выбираем ту, которая содержит достаточно близкие к AB внутренние точки многоугольника P). Число таких полуплоскостей равно числу сторон P, что равно n. Тем самым, в пересечении всех таких полуплоскостей получается выпуклый многоугольник T с количеством сторон не большим n. Докажем, что многоугольник T и является искомым. Во-первых, заметим, что если точка не содержится в какой-нибудь из рассмотренных полуплоскостей, то из неё не видно одной из вершин соответствующей стороны. Во-вторых, докажем, что из любой точки многоугольника T видны все вершины многоугольника P. Предположим противное. Пусть точка B принадлежит T, но из B не видно вершину A. Это значит, что отрезок AB пересекает стороны многоугольника P. Если часть отрезка AB, прилегающая к вершине A, лежит вне многоугольника, то точка B не принадлежит полуплоскости, соответствующей стороне многоуголника с вершиной A. Иначе рассмотрим сторону многоугольника ближайшую к точке A и пересекающую AB, тогда точка B не принадлежит полуплоскости, соответствующей этой стороне. Получили противоречие.

Прислать комментарий

Задача 109552

Темы:	[	Выпуклая оболочка и опорные прямые (плоскости)	]
	[	Выпуклые многоугольники	]
	[	Невыпуклые многоугольники	]
	[	Произвольные многоугольники	]

Сложность: 6-
Классы: 9,10,11

Автор: Берлов С.Л.

Внутри выпуклого стоугольника выбрано k точек, 2 k 50 . Докажите, что можно отметить 2k вершин стоугольника так, чтобы все выбранные точки оказались внутри 2k -угольника с отмеченными вершинами.

Решение

Будем называть выпуклой оболочкой конечного множества точек наименьший выпуклый многоугольник, содержащий все эти точки. Можно доказать, что у любого конечного множества точек существует единственная выпуклая оболочка. Пусть M=A₁A₂.. A_n – выпуклая оболочка выбранных k точек ( n k ), и точка O M отлична от A₁ , A₂ , A_n . Рассмотрим отрезки OA_i и продолжим каждый из них за точку A_i до пересечения с границей стоугольника в точке B_i . Докажем, что M находится внутри выпуклой оболочки M' точек B₁ , B₂ , B_n . Разрежем многоугольник A₁A₂.. A_n на треугольники. Тогда, как легко видеть, если O A_iA_jA_k , то O B_iB_jB_k , а, следовательно, O лежит также и в выпуклой оболочке точек B₁ , B_n . Поскольку A_i лежит внутри отрезка OB_i , то A_i M' , и M лежит внутри M' . Выберем для каждой точки B_i сторону многоугольника, ее содержащую. Рассмотрим множество концов этих сторон. В нем m2n2k точек. Добавим к ним произвольным образом 2k-m вершин стоугольника и рассмотрим 2k -угольник с вершинами в полученных точках. Он выпуклый, его граница содержит точки B₁ , B₂ , B_n и, следовательно, он содержит M' и M .

Прислать комментарий

Задача 111876

Темы:	[	Выпуклая оболочка и опорные прямые (плоскости)	]
	[	Прямоугольники и квадраты. Признаки и свойства	]
	[	Разбиения на пары и группы; биекции	]

Сложность: 6-
Классы: 8,9,10

Автор: Карасев Р.

На плоскости нарисовано несколько прямоугольников со сторонами, параллельными осям координат. Известно, что каждые два прямоугольника можно пересечь вертикальной или горизонтальной прямой. Докажите, что можно провести одну горизонтальную и одну вертикальную прямую так, чтобы любой прямоугольник пересекался хотя бы с одной из этих двух прямых.

Решение

Лемма. Пусть в семействе прямоугольников любые два можно пересечь вертикальной прямой. Тогда их все можно пересечь вертикальной прямой.

Доказательство. Рассмотрим прямоугольник с самой левой правой границей и прямоугольник с самой правой левой границей. По условию их можно пересечь прямой. Тогда у любого из оставшихся прямоугольников левая граница будет левее этой прямой, а правая – правее, то есть прямая пересечет все прямоугольники. Лемма доказана.

Перейдем к решению задачи. Предположим противное. Назовем два прямоугольника разделенными, если их нельзя пересечь вертикальной прямой. Рассмотрим все пары разделенных прямоугольников. В каждой паре рассмотрим прямую, на которой лежит самая нижняя из их горизонтальных сторон; пусть h – самая высокая из этих прямых. Возможны два случая.
1. Пусть не существует пары разделенных прямоугольников, лежащих ниже h . Проведем прямую h и рассмотрим все прямоугольники, не пересеченные ею. Если среди них нет пары разделенных, то по лемме их можно пересечь вертикальной прямой, и утверждение задачи доказано. Пусть такая пара прямоугольников (A,B) нашлась (см. рис.) . Тогда по предположению один из них (скажем, A ) лежит выше h . Из выбора h теперь следует, что нижняя сторона прямоугольника B лежит ниже h , а значит, и весь он лежит ниже h . Значит, эти прямоугольники нельзя пересечь ни вертикальной, ни горизонтальной прямой – противоречие.

2. Пусть существует пара (C,D) разделенных прямоугольников, лежащих ниже h . По выбору h , существуют также два разделенных прямоугольника A и B , лежащие не ниже h . Будем считать, что прямоугольник A лежит левее, чем B , а прямоугольник C – левее, чем D . Пусть для определенности правая сторона A находится не правее, чем правая сторона C (см. рис.) . Тогда прямоугольники A и D также разделены, при этом один из них лежит не ниже h , а другой – ниже h . Значит, эти два прямоугольника нельзя пересечь ни вертикальной, ни горизонтальной прямой. Противоречие.

Прислать комментарий

Задача 58072

Тема:

[

Выпуклая оболочка и опорные прямые (плоскости)

]

Сложность: 6
Классы: 8,9

На плоскости дано n $\ge$ 4 точек, причем никакие три из них не лежат на одной прямой. Докажите, что если для любых трех из них найдется четвертая (тоже из данных), с которой они образуют вершины параллелограмма, то n = 4.

Решение

Рассмотрим выпуклую оболочку данных точек. Возможны два случая.
1. Выпуклая оболочка является параллелограммом ABCD. Если точка M лежит внутри параллелограмма ABCD, то вершины всех трех параллелограммов с вершинами A, B и M лежат вне ABCD (рис.). Значит, в этом случае, кроме точек A, B, C и D, никаких других точек быть не может.

2. Выпуклая оболочка не является параллелограммом. Пусть AB и BC — стороны выпуклой оболочки. Проведем опорные прямые, параллельные AB и BC. Пусть эти опорные прямые проходят через вершины P и Q. Тогда вершины всех трех параллелограммов с вершинами B, P и Q лежат вне выпуклой оболочки (рис.). Они даже лежат вне параллелограмма, образованного опорными прямыми, кроме того случая, когда P и Q являются вершинами этого параллелограмма. В этом случае его четвертая вершина не принадлежит выпуклой оболочке, так как та не является параллелограммом.

Прислать комментарий

Задача 58073

Тема:

[

Выпуклая оболочка и опорные прямые (плоскости)

]

Сложность: 6+
Классы: 8,9

На плоскости дано несколько точек, попарные расстояния между которыми не превосходят 1. Докажите, что эти точки можно покрыть правильным треугольником со стороной $\sqrt{3}$ .

Решение

Рассмотрим три прямые, попарно образующие углы 60^o, и проведем к данному множеству точек три пары опорных прямых, параллельных выбранным прямым. Проведенные опорные прямые задают два правильных треугольника, каждый из которых накрывает данные точки. Докажем, что сторона одного из них не превосходит $\sqrt{3}$ .
На каждой опорной прямой лежит хотя бы одна из данных точек. Расстояние между любой парой данных точек не превосходит 1, поэтому расстояние между любой парой опорных прямых не превосходит 1.
Возьмем одну из данных точек. Пусть a₁, b₁ и c₁ — расстояния от нее до сторон одного правильного треугольника, a₂, b₂ и c₂ — расстояния до сторон другого. При этом мы предполагаем, что a₁ + a₂, b₁ + b₂ и c₁ + c₂ — расстояния между опорными прямыми. Как только что было доказано, a₁ + a₂ $\le$ 1, b₁ + b₂ $\le$ 1 и c₁ + c₂ $\le$ 1. С другой стороны, a₁ + b₁ + c₁ = h₁ и a₂ + b₂ + c₂ = h₂, где h₁ и h₂ — высоты построенных равносторонних треугольников (задача 4.46). Следовательно, h₁ + h₂ $\le$ 3, а значит, одна из высот h₁ и h₂ не превосходит 3/2. Но тогда сторона соответствующего правильного треугольника не превосходит $\sqrt{3}$ .

Прислать комментарий

Страница: << 2 3 4 5 6 7 8 >> [Всего задач: 60]