Задана последовательность чисел $(d_n)$ таких, что $|d_n|\le1$ ($n=1$, $2$, $\ldots$). Докажите, что можно выбрать последовательность $(s_n)$ из чисел $+1$ и $-1$ так, что для всех $n$
$$
|d_1s_1+d_2s_2+\ldots+d_ns_n|\le1.
$$
Задана последовательность троек чисел $(a_n,b_n,c_n)$ таких, что $|a_n|\le1$, $|b_n|\le1$, $|c_n|\le1$ и $a_n+b_n+c_n=0$ ($n=1$, $2$, $\ldots$). По ней строится новая последовательность троек $(x_n, y_n, z_n)$, в которой $x_0=y_0=z_0=0$, а каждая тройка $(x_n,y_n,z_n)$ при $n\ge1$ получается из предыдущей $(x_{n-1},y_{n-1},z_{n-1})$ прибавлением к $x_{n-1}$ одного из чисел $a_n$, $b_n$, $c_n$ по нашему выбору, к $y_{n-1}$ — другого, к $z_{n-1}$ — третьего. Можем ли мы всегда добиться того, что все числа $x_n$, $y_n$, $z_n$ будут по абсолютной величине не больше $1$ или хотя бы ограничены некоторой константой?
Выясните аналогичные вопросы для последовательностей четвёрок чисел.
а) Положим $u_n=s_1d_1+\ldots+s_nd_n$. Числа $s_1$, $s_2$, $\ldots$, $s_n$ можно выбирать по очереди следующим образом: $s_1$ — произвольно; пусть $s_1$, $s_2$, $\ldots$, $s_n$ уже выбраны так, что $|u_k|\le1$ для всех $k=1$, $\ldots$, $n$, тогда $s_{n+1}$ берётся равным $-1$, если числа $u_n$ и $d_{n+1}$ имеют одинаковые знаки, и $+1$, если разные. Совершенно очевидное соображение, которым мы здесь пользуемся, пригодится и в дальнейшем, поэтому сформулируем его в виде леммы:
Лемма.Если два числа имеют разные знаки и каждое по модулю не превосходит $M$, то их сумма по модулю не больше $M$.
Эта лемма применяется к числам $u_n$ и $s_{n+1}d_{n+1}$ (в данном случае $M=1$).
б) Будем называть тройку чисел нормальной, если их сумма равна 0 и каждое не превосходит по модулю 1. Докажем, что можно по очереди «складывать» тройки $(a_n,b_n,c_n)$, переставляя в них числа так, что тройка $(x_n,y_n,z_n)$ будет нормальной при любом $n$. Для этого достаточно заметить, что если тройки $(x,y,z)$ и $(a,b,c)$ нормальны, причём $x\ge y\ge z$ и $a\le b\le c$, то тройка $(x+a,y+b,z+c)$ также нормальна. В самом деле, поскольку $ax\le0$ и $cz\le0$, для сумм крайних чисел неравенства $|a+x|\le1$ и $|c+z|\le1$ выполнены по лемме (при $M=1$), а средние числа по модулю не больше $\dfrac12$ (если $x\le y\le z$, то $x+2y\le x+y+z=0$, поэтому $y\le-\dfrac x2\le\dfrac12$; аналогично доказывается, что $y\ge-\dfrac12$ и что $|b|\le\dfrac12\Big)$.
Задача б) имеет красивую геометрическую интерпретацию. Между тройками чисел с суммой 0 и точками плоскости можно установить соответствие с помощью «системы координат» на плоскости, состоящей из трёх осей $Ox$, $Oy$ и $Oz$, составляющих друг с другом углы величины $120^\circ$; при этом каждой точке $P$ отвечают координаты $x$, $y$ и $z$ её проекций на эти оси (см. рис. 1). Поскольку сумма единичных векторов $\overrightarrow{e_x}$, $\overrightarrow{e_y}$ и $\overrightarrow{e_z}$ равна 0, $x+y+z=\overrightarrow{OP}\cdot\overrightarrow{e_x}+\overrightarrow{OP}\cdot\overrightarrow{e_y}+\overrightarrow{OP}\cdot\overrightarrow{e_z}=\overrightarrow{OP}$ ($\overrightarrow{e_x}+\overrightarrow{e_y}+\overrightarrow{e_z}=0$). Условия $|x|\le1$, $|y|\le1$ и $|z|\le1$ задают три полосы ширины 2, перпендикулярные осям; их пересечение и есть шестиугольник, показанный на рисунке 1.
Рис. 1
Теперь можно пояснить наше решение. Перестановке двух чисел в тройке, т. е. двух координат, отвечает симметрия шестиугольника относительно одной из осей $Ox$, $Oy$, $Oz$, а двум «противоположно упорядоченным» тройкам $(x,y,z)$, $x\ge y\ge z$, и $(a,b,c)$, $a\le b\le c$ — два вектора, лежащие в противоположных — красном и голубом — четырёхугольниках (см. рис. 1). Их сумма всегда лежит внутри шестиугольника, поэтому, если переводить симметриями вектор $(a_n,b_n,c_n)$ в четырёхугольник, противоположный тому, где лежит вектор $(x_{n-1},y_{n-1},z_{n-1})$, прежде чем их складывать, то мы всегда сумеем остаться внутри шестиугольника.
Заметим ещё, что при надлежащем выборе системы координат $OXYZ$ в пространстве, этот же шестиугольник будет сечением куба $\{|X|\le1{,}~|Y|\le1{,}~|Z|\le1\}$ плоскостью $X+Y+Z=0$ (см. рис. 2). При этом координаты любой точки плоскости шестиугольника в системах $Oxyz$ и $OXYZ$ будут совпадать.
Рис. 2
в) Здесь уже нельзя утверждать, что все числа будут по модулю не больше 1, как показывает пример двух четвёрок $(1;1;-1;-1)$ и $\left(\dfrac13;\dfrac13;\dfrac13;-1\right)$: среди их попарных сумм непременно встретится число $\dfrac43=1+\dfrac13$. Однако при операции сложения «переставленных» четвёрок можно получить числа, не превосходящие некоторой постоянной; чтобы это доказать, удобно заменить условие, что числа не превосходят по модулю 1, другим, которое бы сохранялось при такой операции. Вот одно из таких условий:
(*) все числа четвёрки попарно отличаются друг от друга не более чем на 2 (т. е. разность наибольшего и наименьшего не больше 2).
Докажем, что если две четвёрки чисел $x_1\ge x_2\ge x_3\ge x_4$ и $a_1\le a_2\le a_3\le a_4$ удовлетворяют этому условию, то четвёрка $(x_1+a_1{,}~x_2+a_2{,}~x_3+a_3{,}~x_4+a_4)$ ему также удовлетворяет. Пусть $1\le j\lt k\le4$. Тогда разность $(x_j+a_j)-(x_k+a_k)=(x_j-x_k)+(a_j-a_k)$ по модулю не превосходит 2, поскольку числа $x_j-x_k$ и $a_j-a_k$ имеют разные знаки и не превосходят по модулю 2 (лемма из пункта а) при $M=2$). Итак, мы доказали, что можно складывать четвёрки чисел (каждый раз, быть может, переставляя их), так чтобы сохранялось условие (*). Осталось заметить, что в четвёрке чисел с суммой 0, удовлетворяющей этому условию, наибольшее по модулю число не превосходит $\dfrac32$; в самом деле, пусть, например, $x_1\gt\dfrac32$, тогда $x_k\ge x_1-2\gt-\dfrac12$ при $k=2$, 3, 4 и $x_1+x_2+x_3+x_4\gt\dfrac32-\dfrac12-\dfrac12-\dfrac12=0$; аналогично доказывается, что числа $x_j$ не могут быть меньше $-\dfrac32$.
Для $m$-ок чисел при $m\ge5$ дело обстоит так же, как для четвёрок: $m$-ки, полученные из данной последовательности наборов из $m$ чисел, по модулю не больших 1, подходящими перестановками чисел в наборах и сложением, будут удовлетворять условию (*); при этом, если сумма каждого набора равна 0, то все числа по модулю не будут превосходить $2-\dfrac2m$.
Рис. 3. Пересечение трёхмерной «гиперплоскости» $x_1+x_2+x_3+x_4=0$ с четырёхмерным кубом $\lbrace(x_1,x_2,x_3,x_4)\mid|x_i|\le1\mathord,~i=1,2,3,4\rbrace$ — октаэдр (рис. а), а с множеством точек $\lbrace(x_1,x_2,x_3,x_4)\mid|x_i-x_j|\le2\mathord,~1\le i\le j\le4\rbrace$ — многогранник, ограниченный 12 ромбами (рис. б), описанный вокруг этого октаэдра, так что рёбра октаэдра служат длинными диагоналями ромбов; при этом короткие диагонали ромбов образуют каркас куба. Другими, словами, вершины этого 12-гранника — это вершины куба и ещё 6 точек, симметричных центру куба относительно его граней, а плоскости граней 12-гранника делят пополам внешние двугранные углы при рёбрах октаэдра (а также и при рёбрах куба).
На рисунке 3 показана геометрическая интерпретация задачи в). Вместо трёх осей на плоскости, идущих из центра правильного треугольника к его вершинам, надо взять 4 оси в пространстве, направленные к вершинам правильного тетраэдра из его центра. Поскольку сумма единичных векторов этих осей равна 0, каждой точке пространства отвечает четвёрка чисел с нулевой суммой, составленная из координат проекций этой точки на оси $Ox_1$, $Ox_2$, $Ox_3$, $Ox_4$. Условие $|x_i|\le1$ выделяет в пространстве слой толщины 2, заключённый между плоскостями, перпендикулярными осям $Ox_i$; пересечение четырёх таких слоёв есть октаэдр (рис. 3, а). Условие (*) задаёт в пространстве «ромбодекаэдр» — 12-гранник, все грани которого — ромбы (рис. 3, б).
Попробуйте дать геометрическую интерпретацию решению задачи в).
