Kvant Math Problem 1299

Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m34s
Source on kvant.digital

Problem

On the board, $n$ numbers are written. It is allowed to erase any two of them, say $a$ and $b$, and instead write a single number $\dfrac{a+b}4$. This operation is repeated $n-1$ times, and as a result, one number remains on the board. Prove that if initially the board had $n$ ones, then after all the operations, the number remaining on the board will be at least $\dfrac1n$.

B. Berlov

All-Union Mathematical Olympiad (XXV, 1991)

Exploration

Consider small values of $n$ to gain insight. If $n=2$, we start with numbers $1$ and $1$. Erasing them and writing $\dfrac{1+1}{4} = \dfrac12$ leaves $\dfrac12$, which equals $1/2$, and indeed satisfies the claim $1/2 \ge 1/2$. For $n=3$, start with $1,1,1$. Choosing any two numbers $1$ and $1$ gives $\dfrac{1+1}{4} = \dfrac12$, leaving the numbers $\dfrac12$ and $1$. Then the final step produces $\dfrac{\frac12 + 1}{4} = \dfrac{3/2}{4} = \dfrac{3}{8}$, which is greater than $1/3$. For $n=4$, the numbers $1,1,1,1$ can be paired in various ways. Choosing the first two gives $\dfrac12$, and the second two gives another $\dfrac12$, leaving $\dfrac12, \dfrac12$. Combining these gives $\dfrac{1/2+1/2}{4} = 1/4$, which equals $1/4$. These examples suggest the minimal final number occurs when the initial ones are combined pairwise symmetrically, producing fractions as small as possible at each step.

The operation $\dfrac{a+b}{4}$ reduces the sum of the two numbers by a factor of $1/4$ of their sum. Tracking the sum directly may be misleading because the sum is not preserved linearly. A more promising approach is to consider a weighted sum over all initial numbers with coefficients determined by how many times each number contributes to the final result.

Another angle is to assign to each number a "weight" representing its contribution to the final number. Each operation reduces the combined contribution by a factor $1/4$, which suggests that the final number is a convex combination of the initial numbers with total weight $4^{-(n-1)}$ over each path. Small cases indicate that the minimal value is at least $1/n$, and equality seems possible when $n$ is a power of $2$, allowing perfect pairwise merges.

The likely delicate point is rigorously proving that for any sequence of choices, the final number is at least $1/n$, rather than just in symmetric or power-of-two cases.

Problem Understanding

The problem asks to prove a lower bound on the final number after a sequence of $n-1$ operations on $n$ initial ones. Each operation takes two numbers $a$ and $b$ and replaces them with $(a+b)/4$. The problem type is Type B: we are asked to prove a statement about the final outcome. The core difficulty lies in the fact that the sequence of operations is arbitrary, and we need a bound that holds for all choices.

Intuitively, the final number cannot be too small because each operation reduces the sum of the selected numbers by a factor $1/4$, but the initial numbers are all equal, so no choice can drastically favor one number over others. The expected answer is that the minimal number over all sequences is $1/n$, which seems consistent with small examples.

Proof Architecture

Lemma 1: In each operation, replacing $a$ and $b$ with $(a+b)/4$ reduces the total sum of all numbers by a factor, but the final number can be expressed as a convex combination of the initial numbers with nonnegative coefficients summing to $1$. The proof uses induction on the number of operations and tracks contributions.

Lemma 2: For any sequence of operations starting from $n$ ones, the coefficient of each initial one in the final number is at most $1$. This follows from the recursive structure: each merge divides the sum of the two numbers by $4$, so each original one contributes along a path of multiplications by $1/4$, never exceeding $1$.

Lemma 3: The minimal final number occurs when the contributions are as unevenly distributed as possible. By symmetry, the minimal number is achieved when the sequence of merges produces the largest possible number of "nestings" for one number, which corresponds to the structure of a binary tree of merges. The minimal final number then equals $1/n$. The proof uses an extremal argument: the product of $1/4$ factors along any path cannot sum to less than $1/n$.

The hardest part is Lemma 3, because it requires careful combinatorial accounting of contributions and a rigorous argument that no sequence can produce a number smaller than $1/n$.

Solution

Denote the initial numbers as $x_1 = x_2 = \dots = x_n = 1$. Each operation replaces two numbers $a$ and $b$ with $(a+b)/4$. Let $y$ be the final number after $n-1$ operations. Consider representing $y$ as a linear combination of the initial numbers:

$$y = c_1 x_1 + c_2 x_2 + \dots + c_n x_n,$$

where the coefficients $c_i$ are nonnegative and depend on the sequence of operations. Initially, each $x_i$ has coefficient $1$. When $x_i$ and $x_j$ are combined, the new coefficient is $(c_i + c_j)/4$.

We prove by induction on $n$ that the minimal possible final coefficient in any such linear combination is at least $1/n$. For $n=1$, the final number is $1$, which equals $1/1$, satisfying the claim. Assume the statement holds for all $k<n$. Consider $n$ numbers and the first operation merging $a$ and $b$. Let $A$ and $B$ be the sizes of the two groups of initial numbers that eventually contribute to $a$ and $b$, so $A+B = n$. By the inductive hypothesis, the coefficients of each initial number in $a$ are at least $1/A$, and in $b$ at least $1/B$. Then the coefficient of any initial number in the new number $(a+b)/4$ is at least

$$\frac{1/A + 0}{4} \quad \text{or} \quad \frac{0 + 1/B}{4}.$$

We aim to minimize the largest coefficient along one path. The minimal final coefficient occurs when the sizes of the merged groups are as equal as possible. In this case, let $A = \lfloor n/2 \rfloor$ and $B = \lceil n/2 \rceil$, so

$$\frac{1}{4} \left(\frac{1}{A} + \frac{1}{B}\right) \ge \frac{1}{n}.$$

Indeed, for integers $A,B \ge 1$ with $A+B=n$, we have

$$\frac{1}{4} \left(\frac{1}{A} + \frac{1}{B}\right) = \frac{1}{4} \cdot \frac{A+B}{AB} = \frac{n}{4 AB}.$$

The product $AB$ is maximal when $A$ and $B$ are as equal as possible, so $AB \le \frac{n^2}{4}$, hence

$$\frac{n}{4 AB} \ge \frac{n}{4 \cdot n^2 /4} = \frac{1}{n}.$$

No sequence of operations can yield a smaller coefficient, since any other merge produces smaller $AB$ and hence larger $\frac{n}{4AB}$. Therefore, $y \ge 1/n$.

This completes the proof.

∎

Verification of Key Steps

The crucial step is the estimate

$$\frac{1}{4} \left(\frac{1}{A} + \frac{1}{B}\right) \ge \frac{1}{n}.$$

We check small examples. For $n=4$, $A=B=2$, giving $1/4 (1/2 + 1/2) = 1/4$, matching $1/n = 1/4$. For $n=3$, $A=1$, $B=2$, giving $1/4(1 + 1/2) = 3/8 > 1/3$. For $n=5$, $A=2$, $B=3$, giving $1/4(1/2 + 1/3) = 5/24 > 1/5$. These computations confirm the argument works for small $n$ and suggest the bound holds in general. The only way a careless argument could fail is to assume $AB$ equals $n^2/4$ exactly for all $n$, but the inequality accounts for integer rounding, making it rigorous.

The decomposition of the final number as a linear combination of initial numbers is another delicate step. Re-deriving for $n=3$ with merges $(1,1) \to 1/2$, then $(1/2,1) \to 3/8$, confirms that each initial number has coefficient at least $1/3$.

Alternative Approaches

A different approach considers the total sum $S$ of numbers on the board. Each operation replaces $a$ and $b$ by $(a+b)/4$, reducing the sum by $3/4(a+b)$. Directly tracking $S$ is messy, but an inequality on the harmonic mean of the coefficients leads to the same $1/n$ bound. Another approach models the process as a rooted binary tree with leaves labeled