Дано 600 точек на плоскости, никакие три из которых не лежат на одной прямой. Назовем прямую, проходящую ровно через две из них, по обе стороны от которой лежит одинаковое число точек, средней линией. Какое наименьшее число средних линий может быть у данного набора?
Answers & Comments
Verified answer
Вначале докажем, что среднюю линию можно провести через любую точку из этих 600. Действительно, проведем прямую через любые 2 точки (допустим О и X), выберем на ней положительное направление вдоль вектораТак мы продолжаем поворачивать прямую вокруг точки О, проводя ее через следующие точки, до тех пор, пока она не повернется на 180 градусов и вернется в первоначальное положение. Теперь она проходит через те же точки О и Х, только теперь положительное направление оси смотрит в противоположную от Х сторону. В этой ситуации в верхней полуплоскости будет находиться, наоборот, m точек, а в нижней - n. Т.е. число точек в верхней полуплоскости уменьшалось с n до m с шагом не более 1, а в нижней полуплоскости увеличивалось с m до n тоже с шагом не более 1. Соответственно начальная разность n-m между количеством точек в верхней полуплоскости и нижней стала теперь m-n. Заметим, что т.к. m+n=598 - четное число, то n-m - тоже четное и, т.к. разность количеств точек в полуплоскостях изменялась с шагами -2,0,2 с величины n-m до m-n, то в какой-то момент она была равна 0. Это значит, что было положение, когда количество точек в обеих полуплоскостях было одинаковым, т.е. - это и была средняя линия проходящая через точку О. Итак, количество средних линий не меньше, чем количество непересекающихся пар точек, т.е. не меньше 300 (т.к. через каждую точку проходит средняя линия, и одна прямая проходит ровно через 2 точки).
Если точки расположены в вершинах правильного 600-угольника, то понятно, что средние линии - это прямые, соединяющие диаметрально противоположные точки. Их как раз 300 штук.