Question

6. На плоскости отмечено и точек. Докажите, что среди середин всевозможных отрезков с концами в этих точках не менее 2n – 3 различных точек.​

Answer 1

Пусть на плоскости изобразили конечное количество точек и всевозможные середины отрезков с вершинами в данных точках.

Ясно, что раз изначальных точек и середин конечное количество, то всевозможные отрезки с вершинами в данных точках и серединах будут иметь конечное количество значений углов с горизонтом в данной плоскости. Благодаря этому всегда можно провести в данной плоскости такую прямую a, которая образует с горизонтом такой угол x, чтобы угол равный 90° - x отличался от всевозможных углов, которые образуют отрезки с концами в данных точках и серединах.  

Таким образом, если спроецировать все точки и середины на данную прямую, то количество полученных различных проекций будет совпадать с количеством всех различных точек и середин в данной плоскости, ведь из-за отличия угла 90° - x данной прямой со всеми остальными углами не существует такой пары точек, что образовывала бы отрезок, который перпендикулярен прямой a, иначе говоря, никакие две точки не спроецируютcя в одну, при этом из теоремы Фалеса следует, что проекции всех середин являются серединами всех отрезков в вершинах полученных проекций точек.

Как видим, мы смогли свести 2-d задачу к 1-d, то есть осталось доказать, что если на некоторой произвольной прямой обозначить n точек, то получим не менее 2n - 3 середин в отрезках в данных точках.

Покажем, что при добавлении на прямую с самого правого края некоторой новой точки, количество середин увеличится как минимум на 2.

Действительно, добавив новую точку ak+1 cправа от самой правой точки ak, получим новую, cамую правую середину b2 отрезка akak+1 (cмотрите рисунок).

Cередину отрезка ak-1ak обозначим b0, а середину отрезка ak-1ak+1 как b1. Очевидно, что  ak-1ak < ak-1ak+1, то есть середина b1 будет правее середины b0, по тем же самым рассуждениям середина b1 будет левее середины b2.

Как видим, имеем 3 различные не совпадающие друг с другом середины b0,b1,b2. Средина b0 была до добавления справа точки ak+1, а значит с добавлением новой точки ak+1 прибавилось как минимум две новые середины b1 и b2. Все остальные середины находятся левее точки b0 и не могут совпадать с данными тремя точками.

Очевидно, что между двумя точками ровно одна середина, тогда учитывая вышеописанный принцип из n точек можно получить как минимум:  1 + 2(n-2) = 2n-3 различных середин, ведь при прибавлении справа новой точки получаем как минимум две новые середины.

Можно добиться того, чтобы можно было получить ровно 2n-3 середин, для этого все расстояния между соседними точками должны  быть одинаковыми (разбиение отрезка на равные части). В этом случае некоторые середины будут совпадать со всеми не крайними точками, которых n-2, а все остальные середины будут серединами отрезков в соседних точках, которых n-1. Всего: n-2 + n-1 = 2n-3 середины.

Что и требовалось доказать.

Answer 2

Для решения этой задачи воспользуемся методом математической индукции.

База индукции: Пусть у нас имеется 3 точки на плоскости. Тогда количество отрезков с концами в этих точках равно C(3,2) = 3. Среди них есть 3 различные точки - сами точки, а также их середины.

Предположение индукции: Пусть для n точек на плоскости справедливо утверждение о том, что среди середин всех возможных отрезков с концами в этих точках не менее 2n - 3 различных точек.

Шаг индукции: Добавим еще одну точку на плоскости. Теперь у нас имеется n+1 точек. Рассмотрим отрезки, которые имеют один конец в новой точке и другой конец в одной из старых точек. Таких отрезков будет n. Таким образом, у нас есть еще n середин отрезков.

Теперь рассмотрим отрезки, которые имеют оба конца в новой точке. Таких отрезков будет C(n+1,2) = (n+1)n/2. Но некоторые из этих отрезков будут иметь одинаковые середины. Например, отрезок с концами в точках A и B будет иметь ту же середину, что и отрезок с концами в точках B и A. Поэтому количество различных середин этих отрезков будет меньше, чем количество отрезков. Мы можем показать, что количество различных середин отрезков с обоими концами в новой точке равно n.

Таким образом, общее количество различных середин отрезков с концами в n+1 точках будет не менее 2n - 3 + n + n = 2(n+1) - 3.

Таким образом, мы доказали, что среди середин всех возможных отрезков с концами в данных n+1 точках не менее 2(n+1) - 3 различных точек.

Итак, мы доказали утверждение для n=3 и предположили его справедливость для произвольного n. Следовательно, утверждение верно для всех n.