Difference between revisions of "1970 IMO Problems/Problem 3"

Latest revision as of 03:22, 27 November 2024

Problem

The real numbers $a_0, a_1, \ldots, a_n, \ldots$ satisfy the condition:

$1 = a_{0} \leq a_{1} \leq \cdots \leq a_{n} \leq \cdots$ .

The numbers $b_{1}, b_{2}, \ldots, b_n, \ldots$ are defined by

$b_n = \sum_{k=1}^{n} \left( 1 - \frac{a_{k-1}}{a_{k}} \right) \frac{1}{\sqrt{a_k}}$

(a) Prove that $0 \leq b_n < 2$ for all $n$ .

(b) given $c$ with $0 \leq c < 2$ , prove that there exist numbers $a_0, a_1, \ldots$ with the above properties such that $b_n > c$ for large enough $n$ .

Solution

$b_n = \sum_{k=1}^{n} \frac{1 - \frac{a_{k-1}}{a_{k}} }{\sqrt{a_k}} = \sum_{k=1}^{n} \frac{a_k - a_{k-1}}{a_k\sqrt{a_k}} = \sum_{k=1}^{n} (a_k - a_{k-1})\left(a_k^{-\dfrac{3}{2}}\right)$

Let $X_k$ be the rectangle with the verticies: $(a_{k-1},0)$ ; $(a_{k},0)$ ; $(a_{k},a_k^{-\dfrac{3}{2}})$ ; $(a_{k-1},a_k^{-\dfrac{3}{2}})$ .

$[asy] import graph; size(10cm,10cm,IgnoreAspect); Label f; f.p=fontsize(6); xaxis(0,10); yaxis(0,1); real f(real x) { return x^(-3/2); } draw(graph(f,1,10)); draw((1,0)--(1,1)); draw((1,0)--(2,0)--(2,2^(-3/2))--(1,2^(-3/2))--cycle); draw((2,0)--(3,0)--(3,3^(-3/2))--(2,3^(-3/2))--cycle); draw((3,0)--(4,0)--(4,4^(-3/2))--(3,4^(-3/2))--cycle); draw((6,0)--(7,0)--(7,7^(-3/2))--(6,7^(-3/2))--cycle); draw((7,0)--(8,0)--(8,8^(-3/2))--(7,8^(-3/2))--cycle); label("$X_1$",(1.5,0),0.5*N); label("$X_2$",(2.5,0),0.5*N); label("$X_3$",(3.5,0),0.5*N); label("$\cdots$",(5,0),N); label("$X_{n-1}$",(6.5,0),0.5*N); label("$X_n$",(7.5,0),0.5*N); label("$a_0$",(1,0),0.5*S); label("$a_1$",(2,0),0.5*S); label("$a_2$",(3,0),0.5*S); label("$a_3$",(4,0),0.5*S); label("$a_{n-2}$",(6,0),0.5*S); label("$a_{n-1}$",(7,0),0.5*S); label("$a_n$",(8,0),0.5*S); [/asy]$

For all $k \in \mathbb{N}$ , the area of $X_k$ is $(a_k - a_{k-1})\left(a_k^{-\dfrac{3}{2}}\right)$ . Therefore, $b_n = \sum_{k=1}^{n} [X_k]$

For all sequences $\{ a_k \}$ and all $k \in \mathbb{N}$ , $X_k$ lies above the $x$ -axis, below the curve $f(x) = x^{-\dfrac{3}{2}}$ , and in between the lines $x = 1$ and $x = a_n$ , Also, all such rectangles are disjoint.

Thus, $b_n = \sum_{k=1}^{n} [X_k] < \int_{1}^{a_n} x^{-\dfrac{3}{2}} \,dx = \left[-\dfrac{2}{\sqrt{x}}\right]_{1}^{a_n} = 2 - \dfrac{2}{\sqrt{a_n}} < 2$ as desired.

By choosing $a_k = 1 + k (\Delta x)$ , where $\Delta x > 0$ , $b_n$ is a Riemann sum for $\int_{1}^{a_n} x^{-\dfrac{3}{2}} \,dx$ . Thus, $\lim_{\Delta x \to 0^+} b_n = \int_{1}^{a_n} x^{-\dfrac{3}{2}} \,dx$ .

Therefore, $\lim_{n \to \infty} \left[ \lim_{\Delta x \to 0^+} b_n \right] = \lim_{n \to \infty} \int_{1}^{a_n} x^{-\dfrac{3}{2}} \,dx$ $= \lim_{n \to \infty} 2 - \dfrac{2}{\sqrt{a_n}} = \lim_{n \to \infty} 2 - \dfrac{2}{\sqrt{1+n(\Delta x)}} = 2$ .

So for any $c \in [0,2)$ , we can always select a small enough $\Delta x > 0$ to form a sequence $\{ a_n \}$ satisfying the above properties such that $b_n > c$ for large enough $n$ as desired.

Remarks (added by pf02, November 2024)

1. A remark about the problem: it is not a fair problem. It is not a good problem for the International Mathematical Olympiad.

The reason is that the problem is trivial for most anyone who knows a little bit of integral calculus. Taken out of its natural context, it is not trivial. The young people participating in the International Mathematical Olympiad are from an age group whose mathematical education may not have reached calculus, depending on the country they come from. Hence, the problem is more a comparison between mathematical curricula in different countries rather than problem solving ability of young people.

2. The Solution to question (b) of the problem given above is incorrect. Specifically

$\lim_{\Delta x \to 0^+} b_n = \int_{1}^{a_n} x^{-\frac{3}{2}} dx$

is incorrect. (To put it bluntly, it makes no sense!) The upper limit of the integral, $a_n$ depends on $\Delta x$ , so it can not be the result of a limit $\lim_{\Delta x \to 0^+}$ ! In fact, it is not even clear what is meant by $\lim_{\Delta x \to 0^+} b_n$ .

The errors and inconsistencies just continue accumulating and building up in the remainder of the proof.

3. Below, I will give a corrected proof of part (b) of the problem, similar to some extent to the idea the author of the Solution above might have had in mind. Then, I will give a solution which uses no calculus.

Corrected Solution to Part (b) of the Problem

For simplicity of writing and visualizing, let us denote $\epsilon = 2 - c$ . So $c = 2 - \epsilon$ . We need to find a sequence $\{a_k\}$ so that $b_n > 2 - \epsilon$ for $n$ large enough.

We rely on the fact that $b_n = \sum_{k=1}^{n} a_k^{-\frac{3}{2}} (a_k - a_{k-1})$ is a Riemann sum for $\int_{1}^{A} x^{-\frac{3}{2}} dx$ , where $A = a_n$ . The denser the points $\{a_k\}$ , the better the sum approximates the integral.

Since $\int_{1}^{\infty} x^{-\frac{3}{2}} dx = 2$ , we can find $A$ so that $2 - \int_{1}^{A} x^{-\frac{3}{2}} dx < \frac{\epsilon}{2}$ .

Now, we can find a set of points $1 = a_0 < a_1 < \cdots < a_n = A$ in the interval $[1, A]$ , such that the Riemann sum $b_n$ corresponding to these points is as close to the integral as we want, in particular $\int_{1}^{A} x^{-\frac{3}{2}} dx - b_n < \frac{\epsilon}{2}$ .

This proves part (b) of the problem.

(Note that we don't have to, but we can take $a_k = 1 + k \alpha$ as suggested in the Solution. In fact, we can take $\alpha = (A - 1)/N$ and let $N$ be large enough, to make $\alpha$ small enough, to make the Riemann sum close enough to the integral on the interval $[1, A]$ . (Here $\alpha$ stands for the $\Delta x$ in the Solution.))

[Solution by pf02, November 2024]

Solution 2

This is a solution which does not use calculus. Taking in account that $a_{k-1} \le a_k$ we have

$\left( 1 - \frac{a_{k-1}}{a_k} \right) \frac{1}{\sqrt{a_k}} = \frac{a_k - a_{k-1}}{a_k \sqrt{a_k}} \le \frac{a_k - a_{k-1}}{\sqrt{a_{k-1}}\ \sqrt{a_k}\ \frac{\sqrt{a_k} + \sqrt{a_{k-1}}}{2}} = \frac{2(\sqrt{a_k} - \sqrt{a_{k-1}})}{\sqrt{a_{k-1}} \sqrt{a_k}} = 2 \left( \frac{1}{\sqrt{a_{k-1}}} - \frac{1}{\sqrt{a_k}} \right)$

Taking the sum, we get

$b_n = \sum_{k=1}^n \left( 1 - \frac{a_{k-1}}{a_k} \right) \frac{1}{\sqrt{a_k}} \le \sum_{k=1}^n 2 \left( \frac{1}{\sqrt{a_{k-1}}} - \frac{1}{\sqrt{a_k}} \right) = 2 \left( 1 - \frac{1}{\sqrt{a_n}} \right) < 2$ .

This proves (a).

To prove (b), let us take $a_k = 1 + k \alpha$ , with $\alpha >0$ . We do similar tricks:

$\left( 1 - \frac{a_{k-1}}{a_k} \right) \frac{1}{\sqrt{a_k}} = \frac{a_k - a_{k-1}}{a_k \sqrt{a_k}} = \frac{\alpha}{(1 + k \alpha) \sqrt{1 + k \alpha}} \ge$

$\frac{\alpha}{\sqrt{1 + k \alpha}\ \sqrt{1 + (k+1) \alpha}\ \frac{\sqrt{1 + (k+1) \alpha} + \sqrt{1 + k \alpha}}{2}} = \frac{2\alpha (\sqrt{1 + (k+1) \alpha} - \sqrt{1 + k \alpha})}{\sqrt{1 + k \alpha}\ \sqrt{1 + (k+1) \alpha}\ [(1 + (k+1) \alpha) - (1 + k \alpha)]} =$

$2 \left( \frac{1}{\sqrt{1 + k \alpha}} - \frac{1}{\sqrt{1 + (k+1) \alpha}} \right)$

Now take the sum for $k = 1, \cdots, n$ :

$b_n = \sum_{k=1}^n \left( 1 - \frac{a_{k-1}}{a_k} \right) \frac{1}{\sqrt{a_k}} \ge \sum_{k=1}^n \left( \frac{2}{\sqrt{1 + k \alpha}} - \frac{2}{\sqrt{1 + (k+1) \alpha}} \right) = \frac{2}{\sqrt{1 + \alpha}} - \frac{2}{\sqrt{1 + \alpha + n \alpha}}$

For simplicity of writing and visualizing, let us denote $\epsilon = 2 - c$ . So $c = 2 - \epsilon$ . We need to show that we can take $\alpha$ small enough and $n$ large enough so that $2 - b_n < \epsilon$ .

Start by choosing a value for $\alpha$ small enough to make $\frac{2}{\sqrt{1 + \alpha}} > 2 - \frac{\epsilon}{2}$ .

This can be done since this condition amounts to $\sqrt{1 + \alpha} < \frac{4}{4 - \epsilon}$ , or in other words to $\alpha < \left( \frac{4}{4 - \epsilon} \right)^2 - 1$ .

For the chosen value of $\alpha$ we now choose $n$ large enough so that $\frac{2}{\sqrt{1 + \alpha + n \alpha}} < \frac{\epsilon}{2}$ .

This can also be done because the condition amounts to $\sqrt{1 + \alpha + n \alpha} > \frac{4}{\epsilon}$ , or in other words $n > \frac{1}{\alpha}\ \left( \frac{16}{\epsilon^2} - 1 - \alpha \right)$ .

This proves part (b) of the problem.

[Solution by pf02, November 2024]

@@ Line 87: / Line 87: @@
 <math>\lim_{\Delta x \to 0^+} b_n = \int_{1}^{a_n} x^{-\frac{3}{2}} dx</math>
-is incorrect.  (In fact, it makes no sense at all!)  The upper
+is incorrect.  (To put it bluntly, it makes no sense!)  The upper
 limit of the integral, <math>a_n</math> depends on <math>\Delta x</math>, so it can not
-be the result of a <math>\lim_{\Delta x \to 0^+}</math>!  In fact, it is not
+be the result of a limit <math>\lim_{\Delta x \to 0^+}</math>!  In fact, it
-even clear what is meant by <math>\lim_{\Delta x \to 0^+} b_n</math>.
+is not even clear what is meant by <math>\lim_{\Delta x \to 0^+} b_n</math>.
 The errors and inconsistencies just continue accumulating and
-building on in the remainder of the proof.
+building up in the remainder of the proof.
 . Below, I will give a corrected proof of part (b) of the problem,
@@ Line 133: / Line 133: @@
 ==Solution 2==
+This is a solution which does not use calculus.
 Taking in account that <math>a_{k-1} \le a_k</math> we have
-<math>\left( 1 - \frac{a_{k-1}}{a_{k}} \right) \frac{1}{\sqrt{a_k}} =
+<math>\left( 1 - \frac{a_{k-1}}{a_k} \right) \frac{1}{\sqrt{a_k}} =
 \frac{a_k - a_{k-1}}{a_k \sqrt{a_k}} \le
-\frac{a_k - a_{k-1}}{\sqrt{a_{k-1}} \sqrt{a_k} \frac{\sqrt{a_k} + \sqrt{a_{k-1}}}{2}} =
+\frac{a_k - a_{k-1}}{\sqrt{a_{k-1}}\ \sqrt{a_k}\ \frac{\sqrt{a_k} + \sqrt{a_{k-1}}}{2}} =
 \frac{2(\sqrt{a_k} - \sqrt{a_{k-1}})}{\sqrt{a_{k-1}} \sqrt{a_k}} =
 \left( \frac{1}{\sqrt{a_{k-1}}} - \frac{1}{\sqrt{a_k}} \right)</math>
+Taking the sum, we get
+<math>b_n = \sum_{k=1}^n \left( 1 - \frac{a_{k-1}}{a_k} \right) \frac{1}{\sqrt{a_k}} \le
+\sum_{k=1}^n 2 \left( \frac{1}{\sqrt{a_{k-1}}} - \frac{1}{\sqrt{a_k}} \right) =
+\left( 1 - \frac{1}{\sqrt{a_n}} \right) < 2</math>.
+This proves (a).
+To prove (b), let us take <math>a_k = 1 + k \alpha</math>, with <math>\alpha >0</math>. We do similar tricks:
+<math>\left( 1 - \frac{a_{k-1}}{a_k} \right) \frac{1}{\sqrt{a_k}} =
+\frac{a_k - a_{k-1}}{a_k \sqrt{a_k}} =
+\frac{\alpha}{(1 + k \alpha) \sqrt{1 + k \alpha}} \ge</math>
-[TO BE CONTINUED]
+<math>\frac{\alpha}{\sqrt{1 + k \alpha}\ \sqrt{1 + (k+1) \alpha}\ \frac{\sqrt{1 + (k+1) \alpha} + \sqrt{1 + k \alpha}}{2}} =
+\frac{2\alpha (\sqrt{1 + (k+1) \alpha} - \sqrt{1 + k \alpha})}{\sqrt{1 + k \alpha}\ \sqrt{1 + (k+1) \alpha}\ [(1 + (k+1) \alpha) - (1 + k \alpha)]} =</math>
+<math>2 \left( \frac{1}{\sqrt{1 + k \alpha}} - \frac{1}{\sqrt{1 + (k+1) \alpha}} \right)</math>
+Now take the sum for <math>k = 1, \cdots, n</math>:
+<math>b_n = \sum_{k=1}^n \left( 1 - \frac{a_{k-1}}{a_k} \right) \frac{1}{\sqrt{a_k}} \ge
+\sum_{k=1}^n  \left( \frac{2}{\sqrt{1 + k \alpha}} - \frac{2}{\sqrt{1 + (k+1) \alpha}} \right) =
+\frac{2}{\sqrt{1 + \alpha}} - \frac{2}{\sqrt{1 + \alpha + n \alpha}}</math>
+For simplicity of writing and visualizing, let us denote <math>\epsilon = 2 - c</math>.
+So <math>c = 2 - \epsilon</math>.  We need to show that we can take <math>\alpha</math> small enough
+and <math>n</math> large enough so that <math>2 - b_n < \epsilon</math>.
+Start by choosing a value for <math>\alpha</math> small enough to make
+<math>\frac{2}{\sqrt{1 + \alpha}} > 2 - \frac{\epsilon}{2}</math>.
+This can be done since this condition amounts to
+<math>\sqrt{1 + \alpha} < \frac{4}{4 - \epsilon}</math>, or in other words to
+<math>\alpha < \left( \frac{4}{4 - \epsilon} \right)^2 - 1</math>.
+For the chosen value of <math>\alpha</math> we now choose <math>n</math> large enough so that
+<math>\frac{2}{\sqrt{1 + \alpha + n \alpha}} < \frac{\epsilon}{2}</math>.
+This can also be done because the condition amounts to
+<math>\sqrt{1 + \alpha + n \alpha} > \frac{4}{\epsilon}</math>, or in other words
+<math>n > \frac{1}{\alpha}\ \left( \frac{16}{\epsilon^2} - 1 - \alpha \right)</math>.
+This proves part (b) of the problem.
+[Solution by pf02, November 2024]

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

Page

Toolbox

Search