20 точек на плоскости

20 точек на плоскости Условие На плоскости расположены $20$ точек, никакие три из которых не лежат на одной прямой. Нужно соединить некоторые точки отрезками так, чтобы при этом не образовалось ни одного треугольника с вершинами в данных точках. Какое наибольшее число таких отрезков можно провести? Подсказка Рассмотрите точку, соединенную отрезками с наибольшим количеством других точек Решение Ответ: $100$ отрезков Покажем, что можно провести не более $100$ отрезков. Рассмотрим точку, соединенную отрезками с наибольшим количеством других точек. Обозначим это число $k$. Тогда каждая из этих $k$ точек соединена не более, чем с $(20 – k) $ точками, а каждая из этих $(20 – k) $ точек соединена не более, чем с $k$ точками. Отсюда общее число отрезков не больше $\frac{k(20 – k) + (20 – k)k}{2} = 20k – k^2 = $ $ 100 – {(10 – k)}^2$. Сто отрезков можно получить, если разбить совокупность точек на два подмножества по $10$ точек в каждом и соединить отрезком каждые две точки, принадлежащие разным подмножествам http://www.mathforum.ru/forum/read/8/121228/121228/#121228Sun, 13 Sep 2026 07:34:32 +0300 Phorum 5.2.10 http://www.mathforum.ru/forum/read/8/121228/121228/#121228 20 точек на плоскостиhttp://www.mathforum.ru/forum/read/8/121228/121228/#121228Условие

На плоскости расположены $20$ точек, никакие три из которых не лежат на одной прямой. Нужно соединить некоторые точки отрезками так, чтобы при этом не образовалось ни одного треугольника с вершинами в данных точках. Какое наибольшее число таких отрезков можно провести?

Подсказка

Рассмотрите точку, соединенную отрезками с наибольшим количеством других точек

Решение

Ответ: $100$ отрезков
Покажем, что можно провести не более $100$ отрезков.
Рассмотрим точку, соединенную отрезками с наибольшим количеством других точек.
Обозначим это число $k$.
Тогда каждая из этих $k$ точек соединена не более, чем с $(20 – k) $ точками, а каждая из этих $(20 – k) $ точек соединена не более, чем с $k$ точками.
Отсюда общее число отрезков не больше $\frac{k(20 – k) + (20 – k)k}{2} = 20k – k^2 = $ $ 100 – {(10 – k)}^2$.
Сто отрезков можно получить, если разбить совокупность точек на два подмножества по $10$ точек в каждом и соединить отрезком каждые две точки, принадлежащие разным подмножествам

]]> koh Задачки и головоломкиSun, 24 May 2026 23:17:54 +0300