IMO 1973 Problem 6

Proposed by: -
Verified: yes
Verdicts: PASS + PASS
Solve time: 22m47s

Problem

Let $a_1, a_2, \ldots, a_n$ be $n$ positive numbers, and let $q$ be a given real number such that $0 < q < 1$. Find $n$ numbers $b_1, b_2, \ldots, b_n$ for which

(a) $a_k < b_k$ for $k = 1, 2, \ldots, n$,

(b) $q < \tfrac{b_{k+1}}{b_k} < \tfrac {1}{q}$ for $k = 1, 2, \ldots, n - 1$,

Exploration

The previous construction failed because adding a small geometric perturbation to $a_k$ cannot repair arbitrarily bad ratios. Before choosing a new construction, it is necessary to test difficult cases.

For $n=1$, condition (b) is vacuous, and any $b_1>a_1$ with

$$b_1<\frac{1+q}{1-q}a_1$$

works. Since

$$\frac{1+q}{1-q}>1,$$

existence is immediate.

For $n=2$, consider the reviewer’s counterexample:

$$q=\tfrac12,\qquad (a_1,a_2)=(1,100).$$

If one tries to keep $b_1$ close to $a_1$, then condition (b),

$$\frac12<\frac{b_2}{b_1}<2,$$

forces

$$b_2<2b_1,$$

which cannot exceed $100$. Hence any successful construction must sometimes enlarge earlier terms dramatically to support later ones.

This suggests defining $b_k$ recursively so that every term is large enough both to dominate $a_k$ and to satisfy the ratio constraints with nearby terms.

The sum bound

$$\frac{1+q}{1-q}\sum a_k$$

suggests geometric weights. Since

$$1+2q+2q^2+\cdots+2q^{m} < \frac{1+q}{1-q},$$

a natural idea is to spread each $a_i$ across neighboring indices with geometric coefficients. A candidate is

$$b_k=\sum_{i=1}^n a_i q^{|k-i|}.$$

Testing small cases confirms this behaves correctly.

For $n=2$,

$$b_1=a_1+qa_2,\qquad b_2=qa_1+a_2.$$

Then

$$b_2-qb_1=(1-q^2)a_2>0,$$

and

$$b_1-qb_2=(1-q^2)a_1>0,$$

which gives

$$q<\frac{b_2}{b_1}<\frac1q.$$

The sum equals

$$(1+q)(a_1+a_2),$$

which is strictly smaller than

$$\frac{1+q}{1-q}(a_1+a_2).$$

For $n=3$, taking

$$b_1=a_1+qa_2+q^2a_3,$$

$$b_2=qa_1+a_2+qa_3,$$

$$b_3=q^2a_1+qa_2+a_3,$$

one computes

$$b_2-qb_1=(1-q^2)(a_2+qa_3)>0,$$

$$b_1-qb_2=(1-q^2)a_1>0,$$

and similarly for the other adjacent pair. The pattern is stable.

The construction appears to avoid the flaw in the previous proof because the ratio inequalities are built algebraically into the definition, not obtained through a limiting argument.

Problem Understanding

We seek numbers $b_1,\dots,b_n$ satisfying three simultaneous conditions. Each $b_k$ must exceed $a_k$, neighboring terms must satisfy

$$q<\frac{b_{k+1}}{b_k}<\frac1q,$$

and the total sum must remain below

$$\frac{1+q}{1-q}\sum_{k=1}^n a_k.$$

Since condition (b) compares neighboring terms multiplicatively, a construction using geometric coefficients is natural. The difficulty lies in guaranteeing the ratio bounds for arbitrary positive sequences $a_1,\dots,a_n$, including highly unbalanced examples.

Key Observations

Define

$$b_k=\sum_{i=1}^n a_i q^{|k-i|}, \qquad k=1,\dots,n.$$

Each $b_k$ contains $a_k$ with coefficient $1$, and all other terms appear with positive coefficients.

The ratio inequalities can be rewritten as

$$b_{k+1}>qb_k \quad\text{and}\quad b_{k+1}<\frac1q,b_k,$$

equivalently,

$$b_{k+1}-qb_k>0 \quad\text{and}\quad b_k-qb_{k+1}>0.$$

For the proposed construction, these differences telescope into sums with positive coefficients.

The sum condition follows by counting how many times each $a_i$ appears:

$$\sum_{k=1}^n b_k = \sum_{i=1}^n a_i \sum_{k=1}^n q^{|k-i|}.$$

The inner sum is bounded above by the infinite geometric series

$$1+2q+2q^2+\cdots = \frac{1+q}{1-q}.$$

Solution

Define

$$b_k=\sum_{i=1}^n a_i q^{|k-i|}, \qquad k=1,2,\dots,n.$$

We verify the three required properties.

For condition (a), since every $a_i>0$ and the coefficient of $a_k$ in $b_k$ equals $1$,

$$b_k = a_k+\sum_{i\ne k} a_i q^{|k-i|} > a_k.$$

Thus

$$a_k<b_k \qquad (k=1,\dots,n).$$

For condition (b), fix $k\in{1,\dots,n-1}$. We compute

$$b_{k+1}-qb_k.$$

Split the defining sums according to whether $i\le k$ or $i\ge k+1$.

If $i\le k$, then

$$|(k+1)-i|=|k-i|+1,$$

$$q^{|(k+1)-i|} = q,q^{|k-i|}.$$

Hence the contributions from these indices cancel in

$$b_{k+1}-qb_k.$$

If $i\ge k+1$, then

$$|(k+1)-i|=i-k-1, \qquad |k-i|=i-k,$$

$$q^{|(k+1)-i|} -q,q^{|k-i|} = q^{i-k-1}-q^{i-k+1} = (1-q^2)q^{i-k-1}.$$

Therefore

$$b_{k+1}-qb_k = (1-q^2) \sum_{i=k+1}^n a_i q^{i-k-1}.$$

Every term on the right is positive, hence

$$b_{k+1}-qb_k>0.$$

Thus

$$\frac{b_{k+1}}{b_k}>q.$$

Similarly,

$$b_k-qb_{k+1} = (1-q^2) \sum_{i=1}^k a_i q^{k-i}.$$

Again every term is positive, so

$$b_k-qb_{k+1}>0.$$

Thus

$$\frac{b_{k+1}}{b_k}<\frac1q.$$

Combining the two inequalities gives

$$q<\frac{b_{k+1}}{b_k}<\frac1q \qquad (k=1,\dots,n-1).$$

For condition (c),

$$\sum_{k=1}^n b_k = \sum_{k=1}^n \sum_{i=1}^n a_i q^{|k-i|} = \sum_{i=1}^n a_i \sum_{k=1}^n q^{|k-i|}.$$

For fixed $i$,

$$\sum_{k=1}^n q^{|k-i|} = 1+\sum_{r=1}^{i-1}q^r+\sum_{r=1}^{n-i}q^r < 1+2\sum_{r=1}^{\infty}q^r.$$

Since

$$\sum_{r=1}^{\infty}q^r=\frac{q}{1-q},$$

we obtain

$$\sum_{k=1}^n q^{|k-i|} < 1+\frac{2q}{1-q} = \frac{1+q}{1-q}.$$

Hence

$$\sum_{k=1}^n b_k < \frac{1+q}{1-q} \sum_{i=1}^n a_i.$$

The sequence

$$\boxed{ b_k=\sum_{i=1}^n a_i q^{|k-i|} \qquad (k=1,\dots,n) }$$

satisfies all three required conditions.

Verification of Key Steps

The corrected construction survives the counterexample that destroyed the previous proof. Take

$$n=2,\qquad q=\tfrac12,\qquad (a_1,a_2)=(1,100).$$

Then

$$b_1=1+\tfrac12\cdot100=51, \qquad b_2=\tfrac12\cdot1+100=100.5.$$

Thus

$$\frac{b_2}{b_1} = \frac{100.5}{51} \approx1.97,$$

which lies in

$$\left(\tfrac12,2\right).$$

The sum equals

$$151.5,$$

while

$$\frac{1+q}{1-q}(a_1+a_2) = 3\cdot101 = 303.$$

All conditions hold.

For $n=1$, the construction gives

$$b_1=a_1,$$

which does not satisfy strict inequality in (a). The problem requires $b_1>a_1$, so when $n=1$ we replace it by

$$b_1=(1+\varepsilon)a_1$$

for any

$$0<\varepsilon<\frac{2q}{1-q}.$$

Condition (b) is vacuous, and

$$b_1 < \frac{1+q}{1-q}a_1$$

holds. For every $n\ge2$, the original construction already gives strict inequality in (a) because at least one neighboring term contributes positively.

Alternative Approaches

Another successful approach defines $b_k$ recursively as the smallest sequence satisfying both

$$b_k>a_k$$

and

$$b_k>q,b_{k+1}, \qquad b_{k+1}>q,b_k.$$

One can build such a sequence by alternating forward and backward geometric corrections. The proof becomes longer because the global sum estimate requires controlling repeated adjustments. The symmetric convolution

$$b_k=\sum_i a_i q^{|k-i|}$$

builds the ratio constraints directly into the formula and gives the sum bound through a single geometric-series estimate.