Kvant Math Problem 489

The transformation replaces each term by the average of the other two.

kvantmathematicsolympiad

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 1m39s
Source on kvant.digital

Problem

Given three numbers $a$, $b$, $c$. Construct three sequences $(a_n)$, $(b_n)$, $(c_n)$ such that $a_1=a$, $b_1=b$, $c_1=c$ and $$a_{n+1}=\dfrac{b_n+c_n}2,\quad b_{n+1}=\dfrac{c_n+a_n}2,\quad c_{n+1}=\dfrac{a_n+b_n}2$$ for any $n=1$, 2, 3, $\ldots$. Prove that all three sequences have a common limit and find it.

I. Burmistrovich

Exploration

The transformation replaces each term by the average of the other two. Writing a few iterations suggests a balancing effect: large entries decrease while small entries increase, and the triple tends to become equal.

A direct invariant appears when summing coordinates: each new term is an average of two old ones, so the total sum is preserved. This suggests that if a limit exists, it must equal $\frac{a+b+c}{3}$ for each sequence.

The crucial mechanism is not the sum but the evolution of pairwise differences. Computing one difference reveals a simple linear recurrence:

$$a_{n+1}-b_{n+1}=\frac{b_n+c_n}{2}-\frac{c_n+a_n}{2}=\frac{b_n-a_n}{2}.$$

Thus differences shrink in magnitude by a factor of $\frac12$ while alternating sign. This forces convergence of all three sequences to a common value.

The most delicate point is ensuring that convergence of differences suffices to conclude convergence of each sequence, and that the limiting value is compatible with the preserved sum.

Problem Understanding

This is a Type B problem. Three sequences are defined by a symmetric averaging process where each term is replaced by the average of the other two terms.

The core difficulty is to identify the invariant structure and prove convergence of the coupled recurrence. The expected limit is the common average of the initial values, namely $\frac{a+b+c}{3}$, since the total sum is preserved while asymmetry between components decays under iteration.

Proof Architecture

The proof first establishes that the sum $a_n+b_n+c_n$ is invariant under the recurrence. This follows by direct computation of $a_{n+1}+b_{n+1}+c_{n+1}$ in terms of $a_n,b_n,c_n$.

Next, the evolution of pairwise differences $a_n-b_n$, $b_n-c_n$, and $c_n-a_n$ is computed explicitly, each satisfying a linear recurrence with factor $-\frac12$, which implies convergence of all differences to zero.

From vanishing differences, one deduces that all three sequences converge to the same limit $L$.

Finally, the invariant sum identifies $L$ uniquely as $\frac{a+b+c}{3}$.

The most delicate step is the deduction that convergence of differences implies convergence of each sequence and compatibility with the invariant sum.

Solution

Let

$$S_n=a_n+b_n+c_n.$$

Using the recurrence relations,

$$S_{n+1}=\frac{b_n+c_n}{2}+\frac{c_n+a_n}{2}+\frac{a_n+b_n}{2}=\frac{2(a_n+b_n+c_n)}{2}=S_n.$$

Thus $S_n$ is constant, so for all $n$,

$$a_n+b_n+c_n=a+b+c.$$

Consider the difference $a_{n+1}-b_{n+1}$. A direct computation gives

$$a_{n+1}-b_{n+1}=\frac{b_n+c_n}{2}-\frac{c_n+a_n}{2}=\frac{b_n-a_n}{2}.$$

Hence

$$a_{n+1}-b_{n+1}=-\frac12 (a_n-b_n).$$

Iterating this relation yields

$$a_n-b_n=\left(-\frac12\right)^{n-1}(a-b).$$

Similarly,

$$b_{n+1}-c_{n+1}=\frac{c_n+a_n}{2}-\frac{a_n+b_n}{2}=\frac{c_n-b_n}{2}=-\frac12(b_n-c_n),$$

and

$$c_{n+1}-a_{n+1}=\frac{a_n+b_n}{2}-\frac{b_n+c_n}{2}=\frac{a_n-c_n}{2}=-\frac12(c_n-a_n).$$

Thus all pairwise differences satisfy the same recurrence and therefore converge to $0$.

Let $a_n-b_n\to 0$ and $a_n-c_n\to 0$. For any $\varepsilon>0$, there exists $N$ such that for $n\ge N$,

$$|a_n-b_n|<\varepsilon,\quad |a_n-c_n|<\varepsilon.$$

Then $b_n$ and $c_n$ lie within $\varepsilon$ of $a_n$, which implies all three sequences share the same set of limit points. In particular, if $a_n$ converges to $L$, then both $b_n$ and $c_n$ converge to $L$ as well, since their differences from $a_n$ vanish.

To identify $L$, take limits in the invariant sum relation:

$$\lim_{n\to\infty}(a_n+b_n+c_n)=3L=a+b+c.$$

Hence

$$L=\frac{a+b+c}{3}.$$

All three sequences converge and share this common limit.

$$\boxed{\frac{a+b+c}{3}}$$

This completes the proof. ∎

Verification of Key Steps

The identity $a_{n+1}-b_{n+1}=-\frac12(a_n-b_n)$ follows from direct substitution of the recurrence definitions, with cancellation of $c_n$ terms occurring exactly once in each difference.

The conclusion that convergence of differences implies common convergence rests on the estimate that if two sequences differ by a quantity tending to zero and one converges, then the other must converge to the same limit; this follows by bounding their distance from the limiting value.

The identification of the limit uses only the invariance of $S_n$, which is exact for every $n$, ensuring no hidden approximation enters the argument.

Alternative Approaches

A linear algebra formulation treats the recurrence as multiplication by the symmetric matrix with zeros on the diagonal and $\frac12$ elsewhere. The space decomposes into the span of $(1,1,1)$ and its orthogonal complement, where the transformation acts by multiplication by $1$ and $-\frac12$ respectively. This immediately yields convergence to the projection onto $(1,1,1)$, giving the same limit $\frac{a+b+c}{3}$.