Одна задача о расположении точек

26

Одна задача о расположении точек

Г. А. Тоноян

Пусть на плоскости даны $n$ точек, никакие три из которых не лежат на одной прямой (только такие множества точек мы и будем рассматривать). Ясно, что если $n \geq 3$, то можно найти простейший выпуклый *) многоугольник — треугольник — с вершинами в трех из этих точек.

А всегда ли при $n > 3$ можно найти выпуклый четырехугольник с вершинами в этих точках? Если $n = 4$ и точки являются вершинами невыпуклого четырехугольника, то следует это не удостсая. Если же $n \geq 5$, то при любом расположении точек найти выпуклый четырехугольник можно. Действительно, если выпуклой оболочкой нашего множества **) является $k$-угольник, где $k > 3$, все в порядке — любые четыре вершины этого $k$-угольника являются вершинами искомого четырехугольника. Пусть $k = 3$, выпуклой оболочкой является треугольник $ABC$. тогда найдется по крайней мере две точки — $D$ и $E$,— лежащие внутри этого треугольника (см. рис. 1). Примая $DE$ не проходит через вершины треугольника $ABC$. Поэтому две из

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

Рис. 1.

27

Рис. 2.
лочку множества $N \setminus K$ — множества, получающей удалением из $N$ его подмножества $K$, а через $M$ — множество $(N \setminus K) \setminus L$.

Рассмотрим следующие возможности: 1) множество $M$ пусто; 2) множество $M$ состоит из единственной точки; 3) множество $M$ содержит не менее двух точек.

1. Множество $M$ пусто. Тогда $N$ содержит только вершины многоугольников $K$ и $L$, то есть не больше 8 точек (поскольку каждый из многоугольников $K$ и $L$ является треугольником или четырехугольником).

2. Множество $M$ содержит единственный точку; обозначим ее через $P$. Если $L$ — четырехугольник, то проведя одну его диагональ, мы разобем его на два треугольника; точка $P$ лежит внутри одного из них (рис. 3). Обозначим вершины этого треугольника буквами $A, B, C$. Если же $L$ — треугольник, то обозначим

Рис. 3.

его вершины через $A, B, C$; точка $P$ лежит внутри этого треугольника.

В любом случае среди вершин многоугольника $L$ найдет также три вершины $A, B, C$, что $P$ — внутренняя точка треугольника $ABC$.

Проведем из точки $P$ лучи $PA, PB, PC$. Они разбиают плоскость на три угла $APB, BPC, CPA$. Легко видеть, что в каждом из этих углов содержится не более одной вершины многоугольника $K$. В самом деле, пусть, например, угол $APB$ содержит две вершины многоугольника $K$, а значит, содержит некоторую сторону $RQ$ многоугольника $K$. Тогда точки $A, P, B, Q, R$ являются вершинами выпуклого пятугольника (рис. 4), что невозможно. Поэтому $K$ имеет самое большее три вершины (по одной в каждом из рассмотренных углов). Поскольку $L$ имеет, самое большее, четыре вершины, а $M$, по предположению, состоит из одной точки $P$, множество $N$ содержит не более восемми точек.

3. Множество $M$ содержит не менее двух точек. Обозначим через $E$ и $F$ любые две точки множества $M$.

Предположим сначала, что $L$ — четырехугольник. Примяем $EF$ не проходит через вершины многоугольника $L$ и пересекает две его стороны. Если бы $EF$ пересекала две смежные стороны четырехугольника $L$ (рис. 5), то три других вершины $B, C, D$ четырехугольника $L$ вместе с $E$ и $F$ были вершинами выпуклого пятугольника. Следовательно, $EF$ пересека-

28

кает две противоположные стороны четырехугольника $L$.

Пусть, например, луч $EF$ пересекает сторону $AB$, а луч $FE$ пересекает сторону $CD$ (рис. 6). Проведем лучи $FA$, $FB$, $EC$ и $ED$. Вместе с отрезком $EF$ они разбиают плоскость на 4 части. Если бы внутри угла $AFB$ (являющегося одной из этих четырех частей) лежали две вершины многоугольника $K$, а значит, и неоторая сторона $TR$ многоугольника $K$, то точки $A$, $F$, $B$, $T$, $R$ были вершинами выпуклого пятугольника (рис. 7). Следовательно, внутри угла $AFB$ лежит не больше одной вершины многоугольника $K$. Точно так же, внутри угла $CED$ лежит не больше одной вершины многоугольника $K$. Что же касается оставшихся двух частей, то в них восше не могут расположаться вершины многоугольника $K$ (иначе вместе с точки $A$, $F$, $E$, $D$ или $B$, $F$, $E$, $C$ они образованы бы выпуклый пятугольник, рис. 6).

Рис. 5.

Рис. 6.

Рис. 7.

лучается, что $K$ имеет не более двух вершин (по одной внутри углов $AFB$, $CED$), что невозможно, так как $K$ — треугольник или четырехугольник.

Предположим, наконец, что $L$ — треугольник. Примяем $EF$ отделяет одну вершину этого треугольника.

Пусть, например, луч $EF$ пересекает сторону $AB$, а луч $FE$ — сторону $AC$ (рис. 7). Рассудяная, как и прежде, найдем, что в углах $AEC$ и $AFB$ содержится не больше чем по одной вершине многоугольника $K$, а часть плоскости, ограниченная лучами $EC$, $FB$ и отрезком $EF$, совсем не содержит вершин многоугольника $K$.

Итак, предположение, что $M$ содержит не менее двух точек, приводит к противоречию. Если же $M$ пуст или содержит одну точку, то $N$ имеет не более всех точек. Этим и завершается доказательство.

Уражнения

1. Докажите, что если все четырехугольники с вершинами в некоторых $n$ точках — выпуклы, то эти $n$ точек являются вершинами выпуклого $n$-угольника.
2. На плоскости данной $n$ точек. Докажите, что существует не менее $\frac{C_n^3}{n-4}$ выпуклых четырехугольников с вершинами в этих точках.
3. На плоскости данной бесконечное множество точки. Докажите, что при любом $k$ найдется выпуклый $k$-угольник с вершинами в этих точках.
   (Напоминаем, что рассматриваются только такие многоугольники, в которых никакие три точки не лежат на одной прямой.)