Difference between revisions of "1973 IMO Problems/Problem 6"

Revision as of 14:14, 19 September 2025

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

TO BE CONTINUED. SAVING SO I DON'T LOSE WORK DONE SO FAR.

@@ Line 34: / Line 34: @@
 .  The author of the above solution deleted a reference to
-the discussion page [https://aops.com/community/p357934].
+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
@@ Line 45: / Line 45: @@
 ==Solution 1, rewritten and completed==
-Let <math>b_k = 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</math>.
+Let <math>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</math>
+for <math>k = 1, \dots, n</math>.
-For the sake of writing this down, we assumed <math>n \ge 5</math> and
+To make things easy to follow, let us write this explicitly for <math>n = 5</math>:
-<math>2 \le k \le n-2</math>.  To make things easy to follow, let us
-write this explicitly for <math>n = 5</math>:
 <math>b_1 = a_1 + q a_2 + q^2 a_3 + q^3 a_4 + q^4 a_5</math>
@@ Line 60: / Line 60: @@
 <math>b_5 = q^4 a_1 + q^3 a_2 + q^2 a_3 + q a_4 + a_5</math>
+Let us verify that this is indeed a solution to the problem.
+(a) is clearly true.  To verify (b), note that for any <math>k</math> we can suitably
+group terms in the expressions for <math>b_k, b_{k+1}</math> so that <math>b_k = X + Y</math>
+and <math>b_{k+1} = q X + \frac{1}{q}\ Y</math>.
+Then <math>q < \frac{b_{k+1}}{b_k}</math> becomes <math>q < \frac{q X + \frac{1}{q} Y}{X + Y}</math>
+which becomes <math>q X + q Y < q X + \frac{1}{q}\ Y</math> which is true because <math>q < 1</math>.
+Similarly, it is easy to verify that <math>\frac{b_{k+1}}{b_k} < \frac{1}{q}</math>.
+To verify (c), note that when computing <math>b_1 + b_2 + \dots b_n</math> and regrouping
+terms as <math>S_1 a_1 + S_2 a_2 + \dots + S_n a_n</math> each <math>S_k</math> is a sum of <math>1</math> and
+one or two sums of successive powers of <math>q</math>.  More precisely,
+<math>S_k = 1 + \sum_{j = 1}^{n-1} q^j</math> for <math>k = 1</math> and <math>k = n</math>, and
+<math>S_k = 1 + \sum_{j = 1}^{k-1} q^j + \sum_{j = 1}^{n-k} q^j</math> for other <math>k</math>.
+Then <math>S_k < 1 + q(1 + q^2 + ...) + q(1 + q^2 + ...) = 1 + 2 q \frac{1}{1 - q} =
+\frac{1 + q}{1 - q}</math>.
+==Motivation for Solution 1==
+Consider the following related problem:
+Let <math>a_1, a_2, \cdots, a_n</math> be <math>\ge 0</math>, not all <math>= 0</math>, and let <math>q</math> be
+such that <math>0 < q < 1.</math>  Find <math>b_1, b_2, \cdots, b_n</math> such that
+(a) <math>a_k \le b_k</math> for <math>k=1, 2, \cdots, n,</math>
+(b) <math>q \le \frac{b_{k+1}}{b_k} \le \frac{1}{q}</math> for <math>k = 1, 2, \cdots, n-1,</math>
+(c) <math>b_1 + b_2 + \cdots + b_n \le \frac{1+q}{1-q}(a_1 + a_2 + \cdots + a_n).</math>
+To solve this problem, first notice that we have some linearity:
+If <math>B = \{b_1, b_2, \dots, b_n\}</math> is a solution for given
+<math>A = \{a_1, a_2, \dots, a_n\}</math>, and similarly <math>B'</math> is a solution for
+given <math>A'</math>, then <math>\alpha B + \beta B'</math> is a solution for <math>\alpha A + \beta A'</math>
+for any <math>\alpha, \beta > 0</math>.
+Now consider <math>A_k = \{0, 0, \dots, 0, 1, 0, \dots, 0\}</math>, in other words,
+<math>a_k = 1</math> and <math>a_j = 0</math> for <math>j \ne k</math>.  Then
+<math>B_k = \{q^{k-1}, q^{k-2}, \dots, q, 1, q, \dots, q^{n-k}\}</math> is a solution to
+this related problem for <math>A_k</math>.
+Since <math>A = \sum_{k=1}^n a_k A_k</math>, we should take <math>B = \sum_{k=1}^n a_k B_k</math>,
+which is a solution to both the related problem and the given, original
+problem.
+==Solution 2 (following the hint from the discussion page [https://aops.com/community/p357934])==
+In this solution we take
+<math>b_k = a_k + \sum_{j=1}^{\frac{n-1}{2}} q^j (a_{[(k-j) \mod n]} + a_{[(k+j) \mod n]})</math>
+for <math>n</math> odd, and
+<math>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]}</math> for <math>n</math> even.
+To make things easy to follow, let us write this explicitly for <math>n = 5</math>:
+<math>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)</math>
+<math>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)</math>
+<math>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)</math>
+<math>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)</math>
+<math>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)</math>
+and for <math>n = 6</math>:
+<math>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</math>
+<math>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</math>
+<math>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</math>
+<math>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</math>
+<math>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</math>
+<math>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</math>
+Proving that these <math>b_1, b_2, \dots, b_n</math> satisfy (a), (b), (c)
+goes along the same lines as in Solution 1.  The only difference
+is that when comparing <math>b_k</math> and <math>b_{k+1}</math> in the case <math>n</math> odd, we
+note that for any <math>k</math> we can suitably group terms in the expressions
+for <math>b_k, b_{k+1}</math> so that <math>b_k = X + Y + Z</math> and
+<math>b_{k+1} = q X + Y + \frac{1}{q}\ Z</math>.
+Then <math>q < \frac{b_{k+1}}{b_k}</math> becomes
+<math>q < \frac{q X + Y + \frac{1}{q} Z}{X + Y + Z}</math> which becomes
+<math>q X + q Y + q Z < q X + Y + \frac{1}{q}\ Z</math> which is true because <math>q < 1</math>.
+Similarly, it is easy to verify that <math>\frac{b_{k+1}}{b_k} < \frac{1}{q}</math>.
+==Solution 3==

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