1973 IMO Problems/Problem 6

Problem

Let $a_1, a_2,\cdots, 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, \cdots, b_n$ for which

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

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

(c) $b_1+b_2+\cdots+b_n<\dfrac{1+q}{1-q}(a_1+a_2+\cdots+a_n).$

Solution

We notice that the constraints are linear, in the sense that if bi is a solution for ai, q, and bi' is a solution for ai', q, then for any k, k' > 0 a solution for kai + k'ai', q is kbi + k'bi'. Also a "near" solution for ah = 1, other ai = 0 is b1 = qh-1, b2 = qh-2, ... , bh-1 = q, bh = 1, bh+1 = q, ... , bn = qn-h. "Near" because the inequalities in (a) and (b) are not strict.

However, we might reasonably hope that the inequalities would become strict in the linear combination, and indeed that is true. Define br = qr-1a1 + qr-2a2 + ... + qar-1 + ar + qar+1 + ... + qn-ran. Then we may easily verify that (a) - (c) hold.

Remarks (added by pf02, September 2025)

1. The solution above is unacceptable for several reasons:

It is unacceptable to write mathematical text without using parentheses, and writing indexes and powers in the line of text, rather than use subscripts and superscripts. On top of it, the "solution" is incomplete (the author uses "we may easily verify" to justify things which are not straightforward)). It is also imprecise (the author uses the notion of `a "near" solution...' without making it precise enough).

However, after a good amount of scrutiny and guessing, one can see that the text contains a good idea. Below I will rewrite the solution in a way a reader can make sense of it.

2. The author of the above solution deleted a reference to the discussion page https://aops.com/community/p357934. On the discussion page there is an idea for another solution. (In all honesty, it is an idea, or a hint, but it can not be called a solution.)

3. Below I will discuss the above ideas, and give a more general class of solutions to this problem.

Solution 1, rewritten and completed

Let $b_k = \sum_{j = 1}^n q^{k - j} a_j = q^{k-1} a_1 + q^{k-2} a_2 + \dots + a_k + \dots + q^{n-k-1} a_{n-1} + q^{n-k} a_n$ for $k = 1, \dots, n$ .

To make things easy to follow, let us write this explicitly for $n = 5$ :

$b_1 = a_1 + q a_2 + q^2 a_3 + q^3 a_4 + q^4 a_5$

$b_2 = q a_1 + a_2 + q a_3 + q^2 a_4 + q^3 a_5$

$b_3 = q^2 a_1 + q a_2 + a_3 + q a_4 + q^2 a_5$

$b_4 = q^3 a_1 + q^2 a_2 + q a_3 + a_4 + q a_5$

$b_5 = q^4 a_1 + q^3 a_2 + q^2 a_3 + q a_4 + a_5$

Let us verify that this is indeed a solution to the problem.

(a) is clearly true. To verify (b), note that for any $k$ we can suitably group terms in the expressions for $b_k, b_{k+1}$ so that $b_k = X + Y$ and $b_{k+1} = q X + \frac{1}{q}\ Y$ .

Then $q < \frac{b_{k+1}}{b_k}$ becomes $q < \frac{q X + \frac{1}{q} Y}{X + Y}$ which becomes $q X + q Y < q X + \frac{1}{q}\ Y$ which is true because $q < 1$ . Similarly, it is easy to verify that $\frac{b_{k+1}}{b_k} < \frac{1}{q}$ .

To verify (c), note that when computing $b_1 + b_2 + \dots + b_n$ and regrouping terms as $S_1 a_1 + S_2 a_2 + \dots + S_n a_n$ , each $S_k$ is a sum of $1$ and one or two sums of successive powers of $q$ . More precisely,

$S_k = 1 + \sum_{j = 1}^{n-1} q^j$ for $k = 1$ and $k = n$ , and $S_k = 1 + \sum_{j = 1}^{k-1} q^j + \sum_{j = 1}^{n-k} q^j$ for other $k$ .

Then $S_k < 1 + q(1 + q^2 + ...) + q(1 + q^2 + ...) = 1 + 2 q \frac{1}{1 - q} = \frac{1 + q}{1 - q}$ .

Motivation for Solution 1

Consider the following related problem:

Let $a_1, a_2, \cdots, a_n$ be $\ge 0$ , not all $= 0$ , and let $q$ be such that $0 < q < 1.$ Find $b_1, b_2, \cdots, b_n$ such that

(a) $a_k \le b_k$ for $k=1, 2, \cdots, n,$

(b) $q \le \frac{b_{k+1}}{b_k} \le \frac{1}{q}$ for $k = 1, 2, \cdots, n-1,$

(c) $b_1 + b_2 + \cdots + b_n \le \frac{1+q}{1-q}(a_1 + a_2 + \cdots + a_n).$

To solve this problem, first notice that we have some linearity: If $B = \{b_1, b_2, \dots, b_n\}$ is a solution for given $A = \{a_1, a_2, \dots, a_n\}$ , and similarly $B'$ is a solution for given $A'$ , then $\alpha B + \beta B'$ is a solution for $\alpha A + \beta A'$ for any $\alpha, \beta > 0$ .

Now consider $A_k = \{0, 0, \dots, 0, 1, 0, \dots, 0\}$ , in other words, $a_k = 1$ and $a_j = 0$ for $j \ne k$ . Then $B_k = \{q^{k-1}, q^{k-2}, \dots, q, 1, q, \dots, q^{n-k}\}$ is a solution to this related problem for $A_k$ .

Since $A = \sum_{k=1}^n a_k A_k$ , we should take $B = \sum_{k=1}^n a_k B_k$ , which is a solution to both the related problem and the given, original problem.

Solution 2 (following the hint from the discussion page [1])

In this solution we take $b_k = a_k + \sum_{j=1}^{\frac{n-1}{2}} q^j (a_{[(k-j) \mod n]} + a_{[(k+j) \mod n]})$ for $n$ odd, and $b_k = a_k + \sum_{j=1}^{\frac{n}{2}-1} q^j (a_{[(k-j) \mod n]} + a_{[(k+j) \mod n]}) + q^{\frac{n}{2}} a_{[k + \frac{n}{2} \mod n]}$ for $n$ even.

To make things easy to follow, let us write this explicitly for $n = 5$ :

$b_1 = a_1 + q a_2 + q^2 a_3 + q^2 a_4 + q a_5 = a_1 + q (a_5 + a_2) + q^2 (a_4 + a_3)$

$b_2 = q a_1 + a_2 + q a_3 + q^2 a_4 + q^2 a_5 = a_2 + q (a_1 + a_3) + q^2 (a_5 + a_4)$

$b_3 = q^2 a_1 + q a_2 + a_3 + q a_4 + q^2 a_5 = a_3 + q (a_2 + a_4) + q^2 (a_1 + a_5)$

$b_4 = q^2 a_1 + q^2 a_2 + q a_3 + a_4 + q a_5 = a_4 + q (a_3 + a_5) + q^2 (a_2 + a_1)$

$b_5 = q a_1 + q^2 a_2 + q^2 a_3 + q a_4 + a_5 = a_5 + q (a_4 + a_1) + q^2 (a_3 + a_2)$

and for $n = 6$ :

$b_1 = a_1 + q a_2 + q^2 a_3 + q^3 a_4 + q^2 a_5 + q a_6 = a_1 + q (a_6 + a_2) + q^2 (a_5 + a_3) + q^3 a_4$

$b_2 = q a_1 + a_2 + q a_3 + q^2 a_4 + q^3 a_5 + q^2 a_6 = a_2 + q (a_1 + a_3) + q^2 (a_6 + a_4) + q^3 a_5$

$b_3 = q^2 a_1 + q a_2 + a_3 + q a_4 + q^2 a_5 + q^3 a_6 = a_3 + q (a_2 + a_4) + q^2 (a_1 + a_5) + q^3 a_6$

$b_4 = q^3 a_1 + q^2 a_2 + q a_3 + a_4 + q a_5 + q^2 a_6 = a_4 + q (a_3 + a_5) + q^2 (a_2 + a_6) + q^3 a_1$

$b_5 = q^2 a_1 + q^3 a_2 + q^2 a_3 + q a_4 + a_5 + q a_6 = a_5 + q (a_4 + a_6) + q^2 (a_3 + a_1) + q^3 a_2$

$b_6 = q a_1 + q^2 a_2 + q^3 a_3 + q^2 a_4 + q a_5 + a_6 = a_6 + q (a_5 + a_1) + q^2 (a_4 + a_2) + q^3 a_3$

Proving that these $b_1, b_2, \dots, b_n$ satisfy (a), (b), (c) goes along the same lines as in Solution 1. The only difference is that when comparing $b_k$ and $b_{k+1}$ in the case $n$ odd, we note that for any $k$ we can suitably group terms in the expressions for $b_k, b_{k+1}$ so that $b_k = X + Y + Z$ and $b_{k+1} = q X + Y + \frac{1}{q}\ Z$ .

Then $q < \frac{b_{k+1}}{b_k}$ becomes $q < \frac{q X + Y + \frac{1}{q} Z}{X + Y + Z}$ which becomes $q X + q Y + q Z < q X + Y + \frac{1}{q}\ Z$ which is true because $q < 1$ . Similarly, it is easy to verify that $\frac{b_{k+1}}{b_k} < \frac{1}{q}$ .

Solution 3

This solution extracts the essence of the previous solutions, and thus generalizes them.

Think of $B = \{b_1, b_2, \dots, b_n\}$ and $A = \{a_1, a_2, \dots, a_n\}$ as column vectors, and consider the $n \times n$ matrix $Q = (q^{m_{ij}})$ with $m_{ij} \ge 0$ .

The following are sufficient conditions for $Q$ , to imply that $B = Q A$ is a solution to the problem:

(1) The diagonal of $Q$ has only $1$ on it, and the non-diagonal elements of each column of $Q$ are positive powers of $q$ , i.e. $m_{ii} = 0$ and $m_{ij} > 0$ for $i \ne j$ .

(2) Every element of row $k + 1$ of $Q$ is either equal to the corresponding element of row $k$ of $Q$ , or differs from it by a factor of $q$ or of $\frac{1}{q}$ . In other words, for every $j$ , either $m_{(k+1)j} = m_{kj}$ or $m_{(k+1)j} = m_{kj} + 1$ or $m_{(k+1)j} = m_{kj} - 1$ .

(3) Each power of $q$ appears at most twice. In other words, here are no distinct $j_1, j_2, j_3$ such that $m_{j_1k} = m_{j_2k} = m_{j_3k}$ .

Indeed, (1) implies $b_k > a_k$ , so (a) is satisfied. (2) implies that for any $k$ we can suitably group terms in the expressions for $b_k, b_{k+1}$ so that $b_k = X + Y + Z$ and $b_{k+1} = q X + Y + \frac{1}{q}\ Z$ . As we have seen, this implies (b).

(3) implies that when we group terms of $b_1 + b_2 + \dots + b_n$ as $S_1 a_1 + S_2 a_2 + \dots + S_n a_n$ , each $S_k$ is a sum of $1$ and one or two sums of distinct powers of $q$ . More precisely,

Then $S_k = 1 + q^{m_1} (1 + \text{sum of distinct powers of q}) + q^{m_2} (1 + \text{sum of distinct powers of q}) <$

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

This proves (c).

There are very many matrices $Q$ (different from the ones in solutions 1 and 2) satisfying conditions (1), (2) and (3). Just as one example, for $n = 5$ take

$1\ \ \ q\ \ \ q^2\ \ \ q^3\ \ \ q^2$

$q\ \ \ 1\ \ \ q\ \ \ q^2\ \ \ q^3$

$q^2\ \ \ q\ \ \ 1\ \ \ q\ \ \ q^2$

$q^3\ \ \ q^2\ \ \ q\ \ \ 1\ \ \ q$

$q^2\ \ \ q^3\ \ \ q^2\ \ \ q\ \ \ 1$

[Solution by pf02, September 2025]

1973 IMO (Problems) • Resources
Preceded by Problem 5	1 • 2 • 3 • 4 • 5 • 6	Followed by Last Question
All IMO Problems and Solutions

Page

Toolbox

Search