На плоскости дан набор из $n$ векторов, длина каждого из которых не превосходит 1. Докажите, что, заменив некоторые векторы этого набора на противоположные, можно получить такой набор из $n$ векторов, сумма которых имеет длину
не превосходящую $\sqrt n$;
не превосходящую $\sqrt2$.
П. Гусятников, А. Плоткин
Всероссийская математическая олимпиада школьников (1979 год, 9 класс)
Приведём решение задачи б). Оно основано на следующем простом утверждении.
Лемма.Если $\overrightarrow{a}$, $\overrightarrow{b}$, $\overrightarrow{c}$ — векторы на плоскости, по длине не превосходящие $1$, то длина суммы или разности некоторых двух из них также не превосходит $1$.
Действительно, среди шести векторов $\overrightarrow{a}$, $\overrightarrow{b}$, $\overrightarrow{c}$, $-\overrightarrow{a}$, $-\overrightarrow{b}$, $-\overrightarrow{c}$ найдутся два, величина угла между которыми не превосходит $60^\circ$. Но тогда, очевидно, длина разности этих двух векторов не превосходит $1$ (рис. 1).
Рис. 1
Утверждение задачи доказывается теперь так. Пусть $n\gt1$ и $\alpha_n$ — наименьшее число, обладающее таким свойством: для любых векторов $\overrightarrow{a_1}$, $\ldots$, $\overrightarrow{a_n}$ на плоскости, таких, что $|\overrightarrow{a_1}|\le1$, $\ldots$, $|\overrightarrow{a_n}|\le1$, в сумме $\overrightarrow{x}=\pm\overrightarrow{a_1}\pm\ldots\pm\overrightarrow{a_n}$ можно так выбрать знаки, что $|\overrightarrow{x}|\le\alpha_n$. Нам надо проверить, что $\alpha_n\le\sqrt2$. Лемма показывает, что если $n\ge3$, то $\alpha_n=\alpha_{n-1}$. Поэтому $\alpha_n=\alpha_2$. Но, очевидно, $\alpha_2=\sqrt2$ (рис. 2), что и завершает доказательство.
Рис. 2
Любопытно, что доказанный результат (с несколько худшей константой) справедлив и для «неевклидового» способа измерения длин векторов, при котором роль единичного круга играет произвольная выпуклая ограниченная центрально-симметричная фигура $\mathit\Phi$ на плоскости. Этот способ очень популярен в современной математике и состоит в следующем. Чтобы измерить длину $\overrightarrow{a}$, отложим этот вектор от центра симметрии $O$ фигуры $\mathit\Phi$ — пусть $\overrightarrow{a}=\overrightarrow{OA}$ — и найдём наименьшее число $\lambda\ge0$, такое, что $A\in\lambda\mathit\Phi$ ($\lambda\mathit\Phi$ — образ фигуры $\mathit\Phi$ при гомотетии с центром $O$ и коэффициентом $\lambda$ — см. рисунок 3; мы предполагаем, что $\mathit\Phi$ содержит свою границу и что точка $O$ лежит внутри $\mathit\Phi$). Это число $\lambda$ и принимается за «обобщённую длину» $|\overrightarrow{a}|_{\mathit\Phi}$ вектора $\overrightarrow{a}$. Ясно, что если $\mathit\Phi$ — круг радиуса $1$, то $|\overrightarrow{a}|_{\mathit\Phi}=|\overrightarrow{a}|$ и что $|\overrightarrow{OA}|_{\mathit\Phi}\le1$ $\iff$ $A\in\mathit\Phi$. Выражаясь вольно, мы измеряем длины векторов, выбирая различные масштабы по разным направлениям. Легко убедиться в том, что введённое число $|\overrightarrow{a}|_{\mathit\Phi}$ обладает обычными свойствами длины; в частности, справедливо неравенство $|\overrightarrow{a}+\overrightarrow{b}|_{\mathit\Phi}\le|\overrightarrow{a}|_{\mathit\Phi}+|\overrightarrow{b}|_{\mathit\Phi}$. (Проверьте! Здесь вам понадобится выпуклость фигуры $\mathit\Phi$.)
Рис. 3
Аналог доказанного выше утверждения выглядит так. Если $|\overrightarrow{a_1}|_{\mathit\Phi}\le1$, $\ldots$, $|\overrightarrow{a_n}|_{\mathit\Phi}\le1$, то в сумме $\overrightarrow{x}=\pm\overrightarrow{a_1}\pm\ldots\pm\overrightarrow{a_n}$ можно так выбрать знаки, что $|\overrightarrow{x}|_{\mathit\Phi}\le2$.
Доказательство ведётся по той же схеме; нового рассуждения требует лишь доказательство леммы, поскольку мы не можем теперь утверждать, что если $|\overrightarrow{a}|_{\mathit\Phi}\le1$, $|\overrightarrow{b}|_{\mathit\Phi}\le1$ и $(\widehat{\overrightarrow{a},\overrightarrow{b}})\le60^\circ$, то $|\overrightarrow{a}-\overrightarrow{b}|_{\mathit\Phi}\le1$.
Итак, пусть $|\overrightarrow{a}|_{\mathit\Phi}\le1$, $|\overrightarrow{b}|_{\mathit\Phi}\le1$, $|\overrightarrow{c}|_{\mathit\Phi}\le1$. Это означает, что точки $A$, $B$, $C$, такие что $\overrightarrow{OA}=\overrightarrow{a}$, $\overrightarrow{OB}=\overrightarrow{b}$, $\overrightarrow{OC}=\overrightarrow{c}$, принадлежат $\mathit\Phi$.
Пусть $\overrightarrow{OD}=\overrightarrow{a}+\overrightarrow{b}$. Ясно, что, рассматривая возможные положения точки $C$, мы можем ограничиться случаем, когда $C$ принадлежит углу $BOD$. Если при этом $C$ находится в треугольнике $OBD$, то $P_{-\overrightarrow{b}}(C)$ лежит в треугольнике $AOB'$ (здесь $P_{-\overrightarrow{b}}$ — параллельный перенос на вектор $-\overrightarrow{b}$). Следовательно, $P_{-\overrightarrow{b}}(C)\in\mathit\Phi$, так что в этом случае $|\overrightarrow{c}-\overrightarrow{b}|_{\mathit\Phi}\le1$. Оставшуюся часть угла $BOD$ разделим на зоны I и II, как показано на рисунке 4. Если точка $C$ лежит в зоне I, то точка $D$ принадлежит треугольнику $ABC$, лежащему в $\mathit\Phi$, и потому $|\overrightarrow{a}+\overrightarrow{b}|_{\mathit\Phi}\le1$. А если $C$ — в зоне II, то точка $P_{-\overrightarrow{b}}(C)$ принадлежит выпуклому четырёхугольнику $OACB$, лежащему в фигуре $\mathit\Phi$, и мы снова получаем $|\overrightarrow{c}-\overrightarrow{b}|_{\mathit\Phi}\le1$.
Рис. 4
Вводя теперь числа $\alpha_n=\alpha_n(\mathit\Phi)$ как и выше, мы опять видим, что $\alpha_n(\mathit\Phi)=\alpha_2(\mathit\Phi)$ при $n\ge2$. Но $\alpha_2(\mathit\Phi)\le2$, ибо $|\overrightarrow{a_1}+\overrightarrow{a_2}|_{\mathit\Phi}\le|\overrightarrow{a_1}|_{\mathit\Phi}+|\overrightarrow{a_2}|_{\mathit\Phi}\le2$, и потому $\alpha_n(\mathit\Phi)\le2$, что и требовалось. Заметим ещё, что для произвольной фигуры $\mathit\Phi$ константу $2$ уменьшить нельзя: рассмотрите в качестве $\mathit\Phi$ параллелограмм $ABCD$, а в качестве $\overrightarrow{a_1}$ и $\overrightarrow{a_2}$ — векторы $\overrightarrow{OA}$ и $\overrightarrow{OB}$.
