Kvant Math Problem 1196

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m13s
Source on kvant.digital

Problem

Several (at least two) nonzero numbers are given. One may erase any two numbers $a$ and $b$ and write in their place the numbers $a+\dfrac b2$ and $b-\dfrac a2$. Prove that after several such operations it is impossible to obtain the original set of numbers.

D. V. Fomin

Leningrad City Mathematical Olympiad (1989)

Exploration

Denote the transformation applied to a chosen pair $(a,b)$ by

$$(a,b)\mapsto \left(a+\frac b2,; b-\frac a2\right).$$

For two numbers only, the operation is linear with matrix

$$M= \begin{pmatrix} 1 & \frac12\[2mm] -\frac12 & 1 \end{pmatrix}.$$

Its determinant equals

$$\det M=1+\frac14=\frac54.$$

Thus the area scaling factor in the plane is $\frac54$, suggesting that some quadratic quantity is multiplied by $\frac54$.

Compute:

$$\left(a+\frac b2\right)^2+\left(b-\frac a2\right)^2 =a^2+ab+\frac{b^2}{4}+b^2-ab+\frac{a^2}{4} =\frac54(a^2+b^2).$$

So for the selected pair, the sum of squares is multiplied by $\frac54$.

If there are additional numbers, all of them remain unchanged. Hence the total sum of squares of all numbers increases by

$$\frac14(a^2+b^2).$$

Since the numbers involved in an operation are required to be nonzero, this increase is strictly positive.

This immediately suggests an invariant-monovariant argument: the total sum of squares strictly increases after every operation. Returning to the original set of numbers would force the total sum of squares to return to its original value, which is impossible.

The only point that needs checking is that the phrase “original set of numbers” refers to the same collection of numbers, so the sum of their squares is the same. Since the operation never changes the number of entries, equality of the final set with the initial set indeed implies equality of the corresponding sum of squares.

The crucial step is proving strict increase of the total sum of squares after each operation.

Problem Understanding

Several nonzero real numbers are given. At each step one chooses two numbers $a$ and $b$, erases them, and replaces them by

$$a+\frac b2,\qquad b-\frac a2.$$

The task is to prove that after any positive number of such operations one can never obtain again the original collection of numbers.

This is a Type B problem, a pure proof.

The core difficulty is to find a quantity associated with the whole collection that changes in a strictly one-sided manner under every allowed operation.

Proof Architecture

Consider the sum of squares of all numbers in the collection, $S$.

For any chosen pair $(a,b)$, the quantity

$$\left(a+\frac b2\right)^2+\left(b-\frac a2\right)^2$$

equals

$$\frac54(a^2+b^2).$$

This follows by direct expansion.

Consequently, after one operation the total sum of squares changes from $S$ to

$$S+\frac14(a^2+b^2).$$

Since $a$ and $b$ are nonzero, this increment is strictly positive.

Hence the total sum of squares strictly increases after every operation.

If the original collection were obtained again after several operations, the total sum of squares would have to coincide with its initial value, contradicting strict increase.

The lemma most likely to fail under scrutiny is the computation of the change in the sum of squares, so it must be carried out explicitly.

Solution

Let

$$S=x_1^2+x_2^2+\cdots+x_n^2$$

be the sum of the squares of all numbers currently present.

Suppose an operation is performed on the numbers $a$ and $b$. All other numbers remain unchanged, so it suffices to compare the contribution of this pair to $S$ before and after the operation.

Before the operation the contribution is

$$a^2+b^2.$$

After the operation the contribution becomes

$$\left(a+\frac b2\right)^2+\left(b-\frac a2\right)^2.$$

Expanding,

$$\left(a+\frac b2\right)^2+\left(b-\frac a2\right)^2 = a^2+ab+\frac{b^2}{4} +b^2-ab+\frac{a^2}{4}.$$

The mixed terms cancel, yielding

$$\left(a+\frac b2\right)^2+\left(b-\frac a2\right)^2 = \frac54(a^2+b^2).$$

Therefore the total sum of squares changes from $S$ to

$$S-\bigl(a^2+b^2\bigr)+\frac54(a^2+b^2) = S+\frac14(a^2+b^2).$$

The numbers $a$ and $b$ are nonzero, hence

$$a^2+b^2>0.$$

Thus

$$S+\frac14(a^2+b^2)>S.$$

So every operation strictly increases the total sum of squares of all numbers.

Assume that after several operations the original set of numbers is obtained again. The sum of squares of the numbers in that final set is then exactly the same as in the initial set. On the other hand, after each operation the total sum of squares increases strictly, so after any positive number of operations it is strictly larger than its initial value.

This contradiction shows that the original set of numbers cannot be obtained again after several operations.

This completes the proof.

∎

Verification of Key Steps

The first delicate step is the identity

$$\left(a+\frac b2\right)^2+\left(b-\frac a2\right)^2 =\frac54(a^2+b^2).$$

Expanding term by term gives

$$a^2+ab+\frac{b^2}{4}+b^2-ab+\frac{a^2}{4}.$$

The terms $ab$ and $-ab$ cancel exactly. Any sign error here would destroy the argument, since the monotonicity depends on obtaining a fixed positive multiple of $a^2+b^2$.

The second delicate step is proving strict, not merely nonnegative, increase. The increment equals

$$\frac14(a^2+b^2).$$

Because every number in the collection is nonzero, the chosen numbers $a$ and $b$ satisfy

$$a^2+b^2>0.$$

Hence the increment is strictly positive. If zero values were allowed, one would need to check separately whether the increment could vanish.

The final step is the contradiction. Equality of the final collection with the initial collection implies equality of any symmetric quantity computed from the collection, in particular the sum of squares. Since that quantity strictly increases at every operation, it cannot return to its initial value after a positive number of steps.

Alternative Approaches

A linear-algebraic proof is possible. For a chosen pair $(a,b)$, the operation is multiplication by

$$M= \begin{pmatrix} 1 & \frac12\[2mm] -\frac12 & 1 \end{pmatrix}.$$

The matrix satisfies

$$M^{T}M=\frac54,I.$$

Hence the squared Euclidean norm of the chosen pair is multiplied by $\frac54$. The squared norm of the entire vector of all numbers therefore increases by

$$\frac14(a^2+b^2)>0$$

at each step. The remainder of the argument is unchanged.

The direct computation with the sum of squares is preferable because it avoids introducing matrices and exhibits the monotone quantity immediately.