Весенняя Олимпиада
На некоторой плоскости есть четыре города, расположенные в вершинах выпуклого четырехугольника $ABCD$. Города впервые в истории решают провести между собой спортивное соревнование — Весеннюю Олимпиаду. Поскольку ни один из городов изначально не обладает необходимой для Олимпиады инфраструктурой, на то, чтобы быть местом ее проведения, претендует любая точка плоскости (в том числе, и сами города). Каждый город хотел бы, чтобы Олимпиада прошла как можно ближе к нему.
Подпункты
а)
Будем называть точку проведения Олимпиады общественно оптимальной в случае, если сумма расстояний от нее до городов минимальна. Найдите эту общественно оптимальную точку и обоснуйте свой выбор.
б)
Представим себе ситуацию, при которой на голосование городов были бы вынесены две альтернативы: провести Олимпиаду в точке $X$ или провести ее в точке $Y$ (точки $X$ и $Y$ не совпадают). Будем говорить, что точка $X$ побеждает точку $Y$, если при таком голосовании как минимум три города из четырёх голосовали бы за $X$. Найдите множество точек $P$ на данной плоскости, таких, что точку $P$ не побеждает ни одна другая точка, отличная от $P$. Являются ли эти точки общественно оптимальными?
Решение
а) Пусть $O$ точка пересечения диагоналей четырехугольника $ABCD$, а $O_1$ произвольная точка плоскости, отличная от точки $O$. Докажем, что $O_1A+O_1B+O_1C+O_1D > OA+OB+OC+OD$. Если $O_1$ не лежит на прямых $AC$ или $BD$, то, по неравенству треугольника, $O_1A+O_1C > AC=OA+OC$, $O_1B+O_1D > BD=OB+OD$. Сложив почленно эти два неравенства, получим, что $O_1A+O_1B+O_1C+O_1D > OA+OB+OC+OD$. Остается рассмотреть случай, когда $O_1$ лежит на одной из прямых $AC$ или $BD$. Пусть $O_1$ лежит на прямой $AC$. Тогда снова, в силу неравенства треугольника, $O_1B+O_1D > BD=OB+OD$. Так как точки $A,O_1,C$ лежат на одной прямой, то к ним применить неравенство треугольника нельзя. Тем не менее, очевидно, что в этом случае справеливо более слабое неравенство $O_1A+O_1C \geqslant AC=OA+OC$. Сложив почленно два неравенства, снова получим, что $O_1A+O_1B+O_1C+O_1D > OA+OB+OC+OD$. Случай, когда точка $O_1$ лежит на прямой $BD$, рассматривается аналогично. Таким образом, сумма расстояний до всех четырех городов от точки $O$ меньше, чем от точки $O_1$. Значит, $O$ общественно оптимальная точка и других общественно оптимальных точек нет. б) Назовем точку, которую не побеждает никакая другая точка, непобедимой . Докажем, что (i) точка пересечения диагоналей является непобедимой; (ii) никакая другая точка непобедимой не является. (i) Проведем через точку пересечения диагоналей прямые, перпендикулярные им. Эти прямые разобьют плоскость на 4 области, обозначенные за I, II, III, IV. Допустим, на голосование против точки $O$ выносится точка $X$. Окружность с центром в вершине четырехугольника, проходящая через точку O, будет касаться одного из перпендикуляров. Поэтому если точка $X$ принадлежит области I, то за $O$ (и против $X$) будут голосовать как минимум города $A$ и $B$; если точка $X$ принадлежит области II, то за $O$ будут голосовать как минимум города $A$ и $D$; если $X$ принадлежит области III, то за $O$ будут голосовать как минимум города $D$ и $C$, а если $X$ принадлежит области IV, то за $O$ будут голосовать как минимум города $B$ и $С$. Наконец, если точка $X$ лежит на одном из перпендикуляров, то как минимум три города будут голосовать за $O$. Таким образом, точка $O$ действительно непобедимая. (ii) Теперь докажем, что любую другую точку можно победить. Возьмем произвольную точку $X$, не совпадающую с $O$. Опустим из нее перпендикуляр на какую-нибудь диагональ (это всегда можно сделать, ведь $X$ не лежит хотя бы на одной из диагоналей). Обозначим эту диагональ за $d$, а полученную точку за $Y$. Докажем, что точка $Y$ побеждает точку $X$. Заметим, что если на голосование будут вынесены $Y$ и $X$, то города, расположенные в концах диагонали $d$, будут голосовать за Y (перпендикуляр является кратчайшим расстоянием от точки до прямой). Кроме того, за $Y$ обязательно будет голосовать город, расположенный относительно точки $X$ по другую сторону от диагонали $d$. Почему это так? Обозначим этот город за $G$. Заметим, что $\triangle GYX$ тупоугольный, в нем $\angle GYX>90^{\circ}$ по построению. Отсюда следует, что сторона $GX$ в нем самая большая. Следовательно, $GX>GY$, и город $G$ будет голосовать за $Y$. Итак, мы нашли три города, которые будут голосовать за $Y$. Значит, точка $X$ не является непобедимой. Вывод: множество непобедимых точек состоит из одной точки точки пересечения диагоналей. Она, как было показано ранее, является и общественно оптимальной. Дополнительные задания: Придумайте свою «негеографическую» интерпретацию задачи (подсказка: представьте, что есть компания из четырех экономических агентов, которая решает, на каком уровне установить значения неких двух переменных, влияющих на благосостояние каждого из них четырех). Обобщите результаты для выпуклого $n$-угольника, $n \geqslant 3$. При каких $n$ множество непобедимых точек в общем случае непусто (включает хотя бы одну точку)? При каких $n$ какая-нибудь из непобедимых точек будет еще и общественно оптимальной?