Разделы 
Дополнительно
Задача по математике - 262
2014-06-07 
На плоскости отмечены $n + 4$ точки, четыре из которых расположены в вершинах квадрата, а остальные л лежат внутри этого квадрата. Любые из отмеченных точек разрешается соединять отрезками, лишь бы при этом никакой построенный отрезок не содержал отмеченных точек, отличных от его концов, и никакие два из построенных отрезков не имели общих точек, кроме, возможно, концов. Найти наибольшее число отрезков, которые можно построить таким образом.
Решение:
Предположим, что по данным n + 4 точкам уже построена некоторая сеть отрезков, удовлетворяющих условию задачи, причем больше ни одного отрезка провести нельзя (такие сети, называемые в дальнейшем максимальными, обязательно существуют, так как количество всех возможных отрезков ограничено числом $C_{n+4}^{2}$). Многоугольник, вершинами которого служат данные точки, а каждая сторона есть либо отрезок сети, либо объединение нескольких отрезков сети, лежащих на одной прямой, будем называть сетевым. Стороны квадрата К с вершинами в 4 отмеченных точках, внутри которого лежат остальные n точек, всегда принадлежат максимальной сети, так что этот квадрат является сетевым многоугольником. Докажем, что максимальная сеть разбивает квадрат К на сетевые треугольники, каждый из которых содержит ровно три данные точки, а именно его вершины. Рассмотрим произвольную точку О квадрата. Среди всех сетевых многоугольников, содержащих эту точку (множество таких многоугольников не пусто, ибо содержит квадрат К), выберем m-угольник М наименьшей площади. Так как сумма углов многоугольника М равна $180^{\circ}(m - 2)$, то среди его вершин найдется такая вершина А, угол при которой меньше $180^{\circ}$. На каждой из двух сторон этого угла выберем ближайшую и вершине А данную точку, получим тем самым точки B и C (рис.). Отметим, что треугольник АВС содержит данные точки, отличные от А и В, например точку С. Возьмем ту из них - точку D, - для которой угол ABD минимален (если таких точек несколько, то выберем из них ближайшую к точке В). Тогда в треугольнике ABD нет данных точек, отличных от вершин А, В, D, а значит, ни один из отрезков сети не имеет общих точек со сторонами АО и BD, кроме, возможно, этих вершин. В силу максимальности сети отрезки AD и BD ей принадлежат. Таким образом, треугольник ABD сетевой. Если он не совпадает с многоугольники М, то последний разбивается на две части, каждая из которых также является сетевым многоугольником, что противоречит выбору многоугольника М. Поэтому треугольник ABD и есть многоугольник М. Итак, точка О лежит о сетевом треугольнике ABD, не содержащем данных точек, отличных от его вершин. Теперь сосчитаем количество k отрезков в максимальной сети. Для этого найдем сумму всех углов всех треугольников, на которые квадрат К разбит этой сетью. С одной стороны, она равна $180^{\circ} \cdot l$, где $l$ - число треугольников. С другой стороны, она составлена из суммы углов при вершинах квадрата и всех полных углов с вершинами в данных точках внутри квадрата, т. е. равна $360^{\circ}(n + 1)$. Поэтому имеем
$180^{\circ} \cdot l = 360^{\circ}\cdot (n + 1)$,
откуда $l = 2(n + 1)$. Наконец, каждая сторона квадрата К является одной стороной одного, а каждый отрезок сети, отличный от стороны этого квадрата, является общей стороной двух треугольников. Следовательно, получаем равенство $4 + 2(k - 4) = 3l$, откуда
$k = \frac{3}{2}l + 2 = 3n + 5$.
На плоскости отмечены $n + 4$ точки, четыре из которых расположены в вершинах квадрата, а остальные л лежат внутри этого квадрата. Любые из отмеченных точек разрешается соединять отрезками, лишь бы при этом никакой построенный отрезок не содержал отмеченных точек, отличных от его концов, и никакие два из построенных отрезков не имели общих точек, кроме, возможно, концов. Найти наибольшее число отрезков, которые можно построить таким образом.
Решение:
Предположим, что по данным n + 4 точкам уже построена некоторая сеть отрезков, удовлетворяющих условию задачи, причем больше ни одного отрезка провести нельзя (такие сети, называемые в дальнейшем максимальными, обязательно существуют, так как количество всех возможных отрезков ограничено числом $C_{n+4}^{2}$). Многоугольник, вершинами которого служат данные точки, а каждая сторона есть либо отрезок сети, либо объединение нескольких отрезков сети, лежащих на одной прямой, будем называть сетевым. Стороны квадрата К с вершинами в 4 отмеченных точках, внутри которого лежат остальные n точек, всегда принадлежат максимальной сети, так что этот квадрат является сетевым многоугольником. Докажем, что максимальная сеть разбивает квадрат К на сетевые треугольники, каждый из которых содержит ровно три данные точки, а именно его вершины. Рассмотрим произвольную точку О квадрата. Среди всех сетевых многоугольников, содержащих эту точку (множество таких многоугольников не пусто, ибо содержит квадрат К), выберем m-угольник М наименьшей площади. Так как сумма углов многоугольника М равна $180^{\circ}(m - 2)$, то среди его вершин найдется такая вершина А, угол при которой меньше $180^{\circ}$. На каждой из двух сторон этого угла выберем ближайшую и вершине А данную точку, получим тем самым точки B и C (рис.). Отметим, что треугольник АВС содержит данные точки, отличные от А и В, например точку С. Возьмем ту из них - точку D, - для которой угол ABD минимален (если таких точек несколько, то выберем из них ближайшую к точке В). Тогда в треугольнике ABD нет данных точек, отличных от вершин А, В, D, а значит, ни один из отрезков сети не имеет общих точек со сторонами АО и BD, кроме, возможно, этих вершин. В силу максимальности сети отрезки AD и BD ей принадлежат. Таким образом, треугольник ABD сетевой. Если он не совпадает с многоугольники М, то последний разбивается на две части, каждая из которых также является сетевым многоугольником, что противоречит выбору многоугольника М. Поэтому треугольник ABD и есть многоугольник М. Итак, точка О лежит о сетевом треугольнике ABD, не содержащем данных точек, отличных от его вершин. Теперь сосчитаем количество k отрезков в максимальной сети. Для этого найдем сумму всех углов всех треугольников, на которые квадрат К разбит этой сетью. С одной стороны, она равна $180^{\circ} \cdot l$, где $l$ - число треугольников. С другой стороны, она составлена из суммы углов при вершинах квадрата и всех полных углов с вершинами в данных точках внутри квадрата, т. е. равна $360^{\circ}(n + 1)$. Поэтому имеем
$180^{\circ} \cdot l = 360^{\circ}\cdot (n + 1)$,
откуда $l = 2(n + 1)$. Наконец, каждая сторона квадрата К является одной стороной одного, а каждый отрезок сети, отличный от стороны этого квадрата, является общей стороной двух треугольников. Следовательно, получаем равенство $4 + 2(k - 4) = 3l$, откуда
$k = \frac{3}{2}l + 2 = 3n + 5$.
