Весенняя Олимпиада

а) Пусть $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=O_1B+O_1D$. Сложив почленно эти два неравенства, получим, что $O_1A+O_1B+O_1C+O_1D > OA+OB+OC+OD$. Остается рассмотреть случай, когда $O_1$ лежит на одной из прямых $AC$ или $BD$. Пусть $O_1$ лежит на прямой $AC$. Тогда снова, в силу неравенства треугольника, $O_1B+O_1D > BD=O_1B+O_1D$. Так как точки $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$ не является непобедимой.

Вывод: множество непобедимых точек состоит из одной точки точки пересечения диагоналей. Она, как было показано ранее, является и общественно оптимальной.

Дополнительные задания:

item Придумайте свою «негеографическую» интерпретацию задачи (подсказка: представьте, что есть компания из четырех экономических агентов, которая решает, на каком уровне установить значения неких двух переменных, влияющих на благосостояние каждого из них четырех).
item Обобщите результаты для выпуклого $n$-угольника, $n \geqslant 3$. При каких $n$ множество непобедимых точек в общем случае непусто (включает хотя бы одну точку)? При каких $n$ какая-нибудь из непобедимых точек будет еще и общественно оптимальной?