На плоскости расположены $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$ точек в каждом и соединить отрезком каждые две точки, принадлежащие разным подмножествам
