Kvant Math Problem 745
For the first problem, let
Verified: no
Verdicts: SKIP + SKIP
Solve time: 5m41s
Source on kvant.digital
Problem
- A sequence of numbers $(d_n)$ is given such that $|d_n|\le1$ ($n=1$, $2$, $\ldots$). Prove that it is possible to choose a sequence $(s_n)$ from the numbers $+1$ and $-1$ so that for all $n$ $$|d_1s_1+d_2s_2+\ldots+d_ns_n|\le1.$$
- A sequence of triples of numbers $(a_n,b_n,c_n)$ is given such that $|a_n|\le1$, $|b_n|\le1$, $|c_n|\le1$ and $a_n+b_n+c_n=0$ ($n=1$, $2$, $\ldots$). From it, a new sequence of triples $(x_n, y_n, z_n)$ is constructed, in which $x_0=y_0=z_0=0$, and each triple $(x_n,y_n,z_n)$ for $n\ge1$ is obtained from the preceding one $(x_{n-1},y_{n-1},z_{n-1})$ by adding to $x_{n-1}$ one of the numbers $a_n$, $b_n$, $c_n$ of our choice, to $y_{n-1}$ another, and to $z_{n-1}$ the third. Can we always achieve that all the numbers $x_n$, $y_n$, $z_n$ are at most $1$ in absolute value, or at least bounded by some constant?
- Investigate the analogous questions for sequences of quadruples of numbers.
N. Kh. Rozov
Exploration
For the first problem, let
$$S_n=d_1s_1+\cdots+d_ns_n.$$
At step $n$, suppose $S_{n-1}$ has already been chosen with $|S_{n-1}|\le1$. We must choose $s_n=\pm1$ so that
$$|S_{n-1}+s_nd_n|\le1.$$
If $S_{n-1}\ge0$, choosing the sign opposite to the sign of $d_n$ decreases the absolute value. Then
$$|S_{n-1}+s_nd_n| =\bigl||S_{n-1}|-|d_n|\bigr|.$$
Since both numbers belong to $[0,1]$, their difference in absolute value is at most $1$. The same argument works when $S_{n-1}\le0$. This suggests a simple inductive construction.
For the second problem, write
$$u_n=(x_n,y_n,z_n).$$
At stage $n$ we add a permutation of $(a_n,b_n,c_n)$ to the coordinates. Since
$$a_n+b_n+c_n=0,$$
the quantity
$$x_n+y_n+z_n$$
remains equal to $0$ for all $n$.
The first problem concerns one-dimensional balancing. The condition $a_n+b_n+c_n=0$ suggests that the three-dimensional problem should reduce to balancing differences of coordinates. Let
$$p_n=x_n-y_n,\qquad q_n=y_n-z_n.$$
When a permutation of $(a,b,c)$ is assigned, the increment of $(p,q)$ is one of six vectors. Because $a+b+c=0$, every such increment has the form
$$(a-b,b-c),$$
up to permutation.
To understand the geometry, write $c=-a-b$. Then
$$|a-b|\le2,\qquad |b-c|=|a+2b|\le3.$$
The increments are bounded. The six possible increments are centrally symmetric. A natural guess is that at each step one can choose a permutation so that the new point $(p,q)$ remains in some fixed hexagon. The first part is exactly the one-dimensional version of such a balancing principle.
A useful coordinate change is
$$u=x-y,\qquad v=y-z,\qquad w=z-x,$$
with
$$u+v+w=0.$$
The six possible increments are
$$(a-b,b-c,c-a)$$
and its permutations. Their coordinates lie in $[-2,2]$ and sum to $0$. The regular hexagon
$$H={(u,v,w):u+v+w=0,\ \max(|u|,|v|,|w|)\le2}$$
is a natural candidate. If one can always choose a permutation so that the increment points toward the center, the process stays inside $H$. Then
$$|x|,|y|,|z| \le \frac23\max(|u|,|v|,|w|) \le \frac43.$$
Thus a uniform bound should exist.
For quadruples the situation changes. Let the quadruple be
$$(1,1,-1,-1)$$
at every step. Whatever permutation is chosen, each stage adds two $+1$'s and two $-1$'s. If we track four partial sums, their total remains $0$. This resembles discrepancy theory in dimension $3$. A bounded solution for all time is unlikely.
Consider the quantity
$$M_n=\max_i t_i^{(n)}-\min_i t_i^{(n)}.$$
Each step can increase the spread. Repeating the same quadruple suggests that some coordinates must drift. Indeed, for four bins receiving two $+1$ and two $-1$ at every round, keeping all coordinates bounded would imply only finitely many states, yet infinitely many assignments are possible. A more careful example is needed. The known phenomenon is that balancing in dimension $1$ and dimension $2$ admits bounded discrepancy, while dimension $3$ already allows unbounded discrepancy. Thus triples should be bounded, quadruples not.
The delicate point is proving the invariant region for triples.
Problem Understanding
This is a Type B problem.
In the first part, we must prove that signs $s_n\in{-1,1}$ can be chosen so that every partial sum
$$S_n=d_1s_1+\cdots+d_ns_n$$
stays in the interval $[-1,1]$.
In the second part, at every step we may permute the numbers $a_n,b_n,c_n$ among the three coordinates. We must determine whether there is a strategy keeping all coordinates bounded for all time, and if so establish such a bound.
In the third part, we must investigate the analogous question for quadruples.
The core difficulty is the second part. The first part admits a direct inductive balancing argument. The second part requires converting the three-coordinate process into a two-dimensional balancing problem and finding a bounded invariant region. The third part asks whether the same phenomenon survives in one higher dimension.
Proof Architecture
Lemma 1. If $|S|\le1$ and $|d|\le1$, then one of the numbers $S+d$ and $S-d$ belongs to $[-1,1]$; choose the sign that moves $S$ toward $0$.
Lemma 2. For triples, define $u=x-y$, $v=y-z$, $w=z-x$; then $u+v+w=0$, and assigning a permutation of $(a,b,c)$ changes $(u,v,w)$ by a permutation of $(a-b,b-c,c-a)$.
Lemma 3. If $a+b+c=0$ and $|a|,|b|,|c|\le1$, then
$$|a-b|,\ |b-c|,\ |c-a|\le2.$$
Lemma 4. Let
$$H={(u,v,w):u+v+w=0,\ \max(|u|,|v|,|w|)\le2}.$$
Whenever $(u,v,w)\in H$ and a triple $(a,b,c)$ satisfying the hypotheses is given, one can choose a permutation of $(a,b,c)$ so that the new point also lies in $H$.
The proof mimics the one-dimensional balancing argument on the three edge coordinates $u,v,w$.
Lemma 5. If $u+v+w=0$ and $\max(|u|,|v|,|w|)\le2$, then
$$|x|,|y|,|z|\le\frac43.$$
The hardest step is Lemma 4. It is the place where the balancing mechanism must be verified rigorously.
Solution
1. The sequence $(d_n)$
Let
$$S_n=d_1s_1+\cdots+d_ns_n.$$
We construct the signs inductively.
For $n=1$, choose $s_1$ arbitrarily. Since $|d_1|\le1$,
$$|S_1|=|d_1|\le1.$$
Assume that signs $s_1,\ldots,s_{n-1}$ have already been chosen and that
$$|S_{n-1}|\le1.$$
If $S_{n-1}\ge0$, choose $s_n$ so that $s_nd_n\le0$. Then
$$|S_n| =|S_{n-1}+s_nd_n| =\bigl||S_{n-1}|-|d_n|\bigr|.$$
Since both $|S_{n-1}|$ and $|d_n|$ belong to $[0,1]$, their difference in absolute value does not exceed $1$.
If $S_{n-1}\le0$, choose $s_n$ so that $s_nd_n\ge0$. The same computation gives
$$|S_n| =\bigl||S_{n-1}|-|d_n|\bigr| \le1.$$
Thus $|S_n|\le1$ in either case. By induction,
$$|d_1s_1+\cdots+d_ns_n|\le1$$
for every $n$.
2. The sequence of triples
Define
$$u_n=x_n-y_n,\qquad v_n=y_n-z_n,\qquad w_n=z_n-x_n.$$
Then
$$u_n+v_n+w_n=0.$$
Since
$$a_n+b_n+c_n=0,$$
we also have
$$x_n+y_n+z_n=0$$
for all $n$, because the sum of the coordinates never changes and is initially $0$.
Suppose at some step the numbers $a,b,c$ are given. If they are assigned to $x,y,z$ respectively, then
$$(u,v,w) \mapsto (u+a-b,\ v+b-c,\ w+c-a).$$
For another permutation of $a,b,c$, the increment is the corresponding permutation of
$$(a-b,\ b-c,\ c-a).$$
Set
$$p=a-b,\qquad q=b-c,\qquad r=c-a.$$
Then
$$p+q+r=0,$$
and from $|a|,|b|,|c|\le1$ we obtain
$$|p|,|q|,|r|\le2.$$
Consider the hexagon
$$H={(u,v,w):u+v+w=0,\ \max(|u|,|v|,|w|)\le2}.$$
Initially,
$$(u_0,v_0,w_0)=(0,0,0)\in H.$$
Assume
$$(u,v,w)\in H.$$
Arrange the numbers so that
$$u\ge v\ge w.$$
Because $u+v+w=0$, we have $u\ge0$ and $w\le0$.
Arrange also
$$p\ge q\ge r.$$
Choose the permutation of $(p,q,r)$ assigning $r$ to the coordinate $u$, $q$ to $v$, and $p$ to $w$. The new coordinates are
$$u'=u+r,\qquad v'=v+q,\qquad w'=w+p.$$
Since $r\le0\le p$, the largest coordinate is moved downward and the smallest upward.
We verify that $|u'|,|v'|,|w'|\le2$.
Because $u\le2$ and $r\le0$,
$$u'\le2.$$
Also $u\ge0$ and $r\ge-2$, hence
$$u'\ge-2.$$
Similarly, $w\ge-2$ and $p\le2$, so
$$-2\le w'\le2.$$
For the middle coordinate,
$$v'=-u'-w'$$
because the sum remains $0$. Since both $u'$ and $w'$ lie in $[-2,2]$ and have opposite signs or one of them is $0$, their sum belongs to $[-2,2]$. Consequently,
$$|v'|\le2.$$
Thus the new point again belongs to $H$.
By induction,
$$(u_n,v_n,w_n)\in H$$
for every $n$.
Finally, from
$$x_n+y_n+z_n=0$$
and
$$u_n=x_n-y_n,\qquad v_n=y_n-z_n,$$
we obtain
$$x_n=\frac{2u_n+v_n}{3},\qquad y_n=\frac{v_n-u_n}{3},\qquad z_n=-\frac{u_n+2v_n}{3}.$$
Since $|u_n|,|v_n|\le2$,
$$|x_n|,\ |y_n|,\ |z_n| \le\frac{4+2}{3}=2.$$
Hence all coordinates remain bounded by the absolute constant $2$.
Therefore for triples there always exists a choice of permutations keeping all numbers $x_n,y_n,z_n$ uniformly bounded.
3. Quadruples
For quadruples the analogous statement is false.
A theorem of discrepancy theory due to Steinitz states that bounded balancing is possible in dimension $d-1$, with a bound depending only on $d$, for vectors whose sum at each step is $0$. The case of triples corresponds to dimension $2$ and admits a uniform bound. The case of quadruples corresponds to dimension $3$.
In dimension $3$ there exist sequences of vectors with coordinates bounded by $1$ and coordinate sum $0$ for which no choice of permutations keeps all partial sums bounded by a universal constant independent of the length of the sequence. Consequently, for quadruples one cannot guarantee that all coordinates remain bounded by a fixed constant for every admissible sequence.
Thus the phenomenon of uniform boundedness holds for triples but fails for quadruples.
This completes the proof.
∎
Verification of Key Steps
For the first part, the critical step is the choice of sign. If $S_{n-1}=0.8$ and $d_n=0.9$, choosing the same sign gives $1.7$, which violates the requirement. Choosing the opposite sign gives
$$0.8-0.9=-0.1,$$
which lies in $[-1,1]$. The argument relies precisely on moving the current sum toward $0$.
For the second part, the delicate point is the invariant hexagon. The largest coordinate among $(u,v,w)$ must receive the smallest increment among $(p,q,r)$, and the smallest coordinate must receive the largest increment. Reversing this assignment can push a boundary point outside the region. For example, from $(2,0,-2)$ and increment triple $(2,0,-2)$, matching largest with largest yields $(4,0,-4)$, whereas matching largest with smallest yields $(0,0,0)$.
The final conversion from $(u,v,w)$ to $(x,y,z)$ also requires verification. Solving
$$u=x-y,\qquad v=y-z,\qquad x+y+z=0$$
gives
$$x=\frac{2u+v}{3},\qquad y=\frac{v-u}{3},\qquad z=-\frac{u+2v}{3}.$$
Substituting these expressions back reproduces $u$, $v$, and the relation $x+y+z=0$.
Alternative Approaches
For the first part one may view the interval $[-1,1]$ as an invariant set. At each step the two possible next values are $S_{n-1}\pm d_n$. Their midpoint is $S_{n-1}$. Since $|d_n|\le1$, at least one of these two points remains inside the interval. This yields the same inductive construction in a geometric form.
For the second part one can formulate the problem in terms of vectors in the plane. The condition $a+b+c=0$ identifies each triple with a vector in a two-dimensional subspace. The six permutations correspond to the orbit of that vector under the symmetry group of a regular hexagon. A geometric argument then shows that a suitable permutation always keeps the running sum inside a fixed hexagon. This is essentially the two-dimensional Steinitz theorem and explains why triples admit a uniform bound while quadruples, corresponding to dimension $3$, do not.