Question

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

Answer 1

Ответ: 9*8/2 = 36.
Решение. Пример, когда треугольников именно столько, получается, если рассмотреть все треугольники с вершиной в данной точке А: у каждого из них сторона, противолежащая вершине А, уникальна, т.е. не входит ни в какой другой из них. Покажем, что большего числа треугольников выбрать не удастся. Каждый отрезок с концами в данных точках входит в 8 треугольников с вершинами в данных точках. Всего отрезков с концами в данных 10 точках имеется 10*9/2 = 45. Если выбрано больше 36 треугольнbков, то неуникальных сторон будет не больше, чем 45 – 37 = 8, и каждая считается в составе выбранных треугольников не больше 8 раз. Поэтому всего у выбранных треугольников должно быть не больше 8*8+37 = 101 сторон. Однако, на самом деле их 3*37 = 111. Противоречие