Kvant Math Problem 114
Let the numbers around the circle be $x_1,x_2,\dots,x_n$, with indices taken modulo $n$.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m56s
Source on kvant.digital
Problem
Several numbers are written around a circle. If for some four consecutive numbers $a$, $b$, $c$, $d$ it turns out that $(a-b)(c-d)\lt0$, then the numbers $b$ and $c$ may be interchanged. Prove that this operation can be performed only finitely many times.
V. B. Alekseev
Exploration
Let the numbers around the circle be $x_1,x_2,\dots,x_n$, with indices taken modulo $n$. The allowed move exchanges $x_i$ and $x_{i+1}$ provided
$$(x_{i-1}-x_i)(x_{i+1}-x_{i+2})<0.$$
This means that the two adjacent differences on the outside have opposite signs. Equivalently, either
$$x_{i-1}>x_i \quad \text{and} \quad x_{i+1}<x_{i+2},$$
or
$$x_{i-1}<x_i \quad \text{and} \quad x_{i+1}>x_{i+2}.$$
The first instinct is to search for a monotone quantity. Since the operation swaps adjacent entries, the number of inversions is a natural candidate. Testing small examples shows it does not always decrease.
Take
$$(4,1,3,2).$$
The move applies to the quadruple $(4,1,3,2)$ because
$$(4-1)(3-2)>0,$$
so this is not allowed. Instead consider
$$(4,1,2,3).$$
Then
$$(4-1)(2-3)<0,$$
and swapping $1,2$ gives
$$(4,2,1,3).$$
The inversion count changes from $3$ to $4$. Thus inversions fail.
Another possibility is the sum of squares of neighboring differences,
$$\sum (x_i-x_{i+1})^2.$$
A direct computation after swapping $b,c$ changes only four terms:
$$(a-b)^2+(b-c)^2+(c-d)^2$$
becomes
$$(a-c)^2+(b-c)^2+(b-d)^2.$$
The difference equals
$$(a-c)^2+(b-d)^2-(a-b)^2-(c-d)^2.$$
Expanding gives
$$2(a-b)(b-c)+2(c-d)(c-b).$$
Factorizing,
$$2(b-c)\bigl((a-b)-(c-d)\bigr).$$
This has no fixed sign.
Try concrete numbers. With $(4,1,2,3)$ the old value is
$$9+1+1=11,$$
the new value is
$$4+1+1=6.$$
So it decreases there. But another example may increase it.
A more promising idea is to examine the number of sign changes in the cyclic sequence of differences
$$x_1-x_2,\ x_2-x_3,\ \dots,\ x_n-x_1.$$
The condition says the two outer differences have opposite signs. After the swap, the middle difference changes sign:
$$b-c \mapsto c-b.$$
This suggests some local simplification.
Still, sign changes alone are bounded but need not strictly decrease.
Another standard trick for finite termination problems is to find a lexicographically increasing quantity. Since only adjacent entries are swapped, perhaps some weighted sum works.
Consider
$$F=\sum_{i=1}^n i x_i.$$
After swapping adjacent $b=x_i$ and $c=x_{i+1}$,
$$F' - F = i c +(i+1)b - \bigl(i b +(i+1)c\bigr)=b-c.$$
The move condition contains no information about the sign of $b-c$, so this is inconclusive.
Try instead
$$E=\sum (x_i-x_{i+1})^2.$$
Recompute carefully. Before:
$$(a-b)^2+(b-c)^2+(c-d)^2.$$
After:
$$(a-c)^2+(c-b)^2+(b-d)^2.$$
Since $(c-b)^2=(b-c)^2$, the change is
\begin{align*}
\Delta
&=(a-c)^2+(b-d)^2-(a-b)^2-(c-d)^2 \
&=(b-c)\bigl(2a-2d+2c-2b\bigr) \
&=2(b-c)(a-b+c-d).
\end{align*}
Now the move condition says $(a-b)(c-d)<0$, so $a-b$ and $c-d$ have opposite signs. Hence
$$|a-b+c-d|<|b-c|?$$
No, that is unsupported.
Try another invariant. Expanding
$$\sum (x_i-x_{i+1})^2 = 2\sum x_i^2-2\sum x_ix_{i+1}.$$
The sum of squares is fixed, so the behavior depends on
$$P=\sum x_ix_{i+1}.$$
After swapping $b,c$,
$$P' - P = ac+bd-ab-cd=(a-d)(c-b).$$
The move condition gives
$$(a-b)(c-d)<0.$$
This still does not determine the sign.
Try ordering relations. The operation exchanges $b,c$ when the neighbors force them into the opposite local trend. Suppose $b<c$. Then for the move to occur we need either
$$a>b,\quad c<d,$$
or
$$a<b,\quad c>d.$$
In the first case,
$$a>b<c<d,$$
so the pair $(b,c)$ is already increasing. In the second,
$$a<b
No monotonicity there.
Perhaps the crucial quantity is the number of cyclic descents
$$D=#{i:x_i>x_{i+1}}.$$
Swapping $b,c$ only changes the three adjacent comparisons. Compute systematically.
Before:
$$a\ ?\ b,\quad b\ ?\ c,\quad c\ ?\ d.$$
After:
$$a\ ?\ c,\quad c\ ?\ b,\quad b\ ?\ d.$$
Take the allowed pattern
$$a>b,\quad c<d.$$
If also $b<c$, then initially there is one descent among the three edges, namely $a>b$. After swapping,
$$a\ ?\ c,\quad c>b,\quad b\ ?\ d.$$
Now $c>b$ is a descent, and perhaps $a>c$ too. The number need not decrease.
Another idea is that every move decreases the number of cyclically ordered triples. But that seems complicated.
A direct computation with the product
$$Q=\prod_{i=1}^n (x_i-x_{i+1})$$
fails because one factor changes sign, so $Q$ changes sign.
The condition resembles bubble sorting constrained by local slopes. Perhaps every move decreases the number of alternating patterns. Define
$$s_i=\operatorname{sgn}(x_i-x_{i+1}).$$
A move at $(a,b,c,d)$ requires
$$s_{i-1}s_{i+1}<0.$$
After swapping, the three relevant signs become
$$\operatorname{sgn}(a-c),\ -s_i,\ \operatorname{sgn}(b-d).$$
Test examples numerically. Take
$$4,1,2,3.$$
Signs are
$$+,-,-,+.$$
After swapping:
$$4,2,1,3,$$
signs become
$$+,+,-,-.$$
The number of sign changes drops from $2$ to $1$ cyclically.
Take another example:
$$1,3,2,4.$$
Signs:
$$-,+,-,+.$$
Swap $3,2$:
$$1,2,3,4,$$
signs:
$$-,-,-,+.$$
Again the number of sign changes drops.
This looks promising. Around the affected region, the pattern before is either
$$+,\ *,\ -,$$
or
$$-,\ *,\ +.$$
After the swap, perhaps the three signs become all equal except possibly one. The key point is to prove the number of sign changes strictly decreases.
Need careful treatment of equalities. Since the condition is strict, the outer differences are nonzero, but $b-c$ may be zero. If $b=c$, swapping changes nothing, so infinite repetitions become possible by repeating the trivial move. Thus the intended interpretation must exclude vacuous swaps, or perhaps equal numbers cannot create a legal move? Check:
$$(a-b)(b-d)<0$$
when $c=b$.
Possible, for instance $a=3,b=c=1,d=2$ gives
$$(2)(-1)<0.$$
Swapping equal numbers does nothing, hence infinitely many operations are formally possible. So the problem implicitly means operations that change the configuration. The proof should mention this subtlety. Better: if equal adjacent numbers are swapped, the arrangement is unchanged, so such moves may be ignored. We only need show that nontrivial changes occur finitely many times.
Now prove sign changes decrease. Let
$$s_1,\dots,s_n$$
be the signs of consecutive differences, ignoring zeros carefully. Since only finitely many nonzero sign changes exist, strict decrease gives termination.
Need a robust definition handling zeros. Better define
$$T=#{i:(x_i-x_{i+1})(x_{i+1}-x_{i+2})<0},$$
the number of local extrema. Perhaps each move decreases $T$.
But examples suggest the cyclic sign change count works cleanly.