Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1985 IMO Problems/Problem 6"
(→‎Solution 3)
Line 47: Line 47:
  
 
Let's first show uniqueness. Suppose that <math>\{x_n\}</math> and <math>\{y_n\}</math> are both such sequences. We have <math>\lim_{n\to\infty}x_n=\lim_{n\to\infty}y_n=1</math> and suppose that <math>y_1>x_1</math>. Then for all <math>n</math>,
 
Let's first show uniqueness. Suppose that <math>\{x_n\}</math> and <math>\{y_n\}</math> are both such sequences. We have <math>\lim_{n\to\infty}x_n=\lim_{n\to\infty}y_n=1</math> and suppose that <math>y_1>x_1</math>. Then for all <math>n</math>,
−
\[
+
<cmath>\frac{y_{n+1}}{x_{n+1}} = \frac{y_n(y_n+\frac 1n)}{x_n(x_n+\frac 1n)}>\frac{y_n}{x_n}</cmath> so inductively, <math>\frac{y_{n+1}}{x_{n+1}}>(\frac{y_{1}}{x_{1}})^n</math> with <math>\lim_{n\to\infty}\frac{y_{n+1}}{x_{n+1}}=+\infty</math>.
−
\frac{y_{n+1}}{x_{n+1}} = \frac{y_n(y_n+\frac 1n)}{x_n(x_n+\frac 1n)}>\frac{y_n}{x_n}
 
−
\]so inductively, <math>\frac{y_{n+1}}{x_{n+1}}>(\frac{y_{1}}{x_{1}})^n</math> with <math>\lim_{n\to\infty}\frac{y_{n+1}}{x_{n+1}}=+\infty</math>.
 
 
However, <math>\lim_{n\to\infty}x_n=\lim_{n\to\infty}y_n=1</math> gives <math>\lim_{n\to\infty}\frac{y_{n+1}}{x_{n+1}}=\frac{1}{1}=1</math>, contradiction.
 
However, <math>\lim_{n\to\infty}x_n=\lim_{n\to\infty}y_n=1</math> gives <math>\lim_{n\to\infty}\frac{y_{n+1}}{x_{n+1}}=\frac{1}{1}=1</math>, contradiction.
 
Hence, the <math>x_1</math> that satisfies this must be unique.
 
Hence, the <math>x_1</math> that satisfies this must be unique.

Revision as of 23:02, 29 January 2021

Problem

For every real number $x_1$, construct the sequence $x_1,x_2,\ldots$ by setting $x_{n+1}=x_n \left(x_n + \frac{1}{n}\right)$ for each $n \geq 1$. Prove that there exists exactly one value of $x_1$ for which $0<x_n<x_{n+1}<1$ for every $n$.

Solution 1

By recursive substitution, one can write $x_n=P_n(x_1)$ , where $P_n$ is a polynomial with non-negative coefficients and zero constant term. Thus, $P_n(0)=0$, $P_n$ is strictly increasing in $[0,+\infty)$ , and $\displaystyle \lim_{x_1 \rightarrow + \infty} P_n(x_1)=+\infty$. We can therefore define the inverse $P_n^{-1}$ of $P_n$ on $[0,+\infty)$. It follows that $x_1=P_n^{-1}(x_n)$, $P_n^{-1}(0)=0$, $P_n^{-1}$ is strictly increasing in $[0,+\infty)$, and $\displaystyle \lim_{x_1 \rightarrow + \infty} P_n^{-1}(x_1) =+\infty$.

Denote by $\displaystyle a_n=P_n^{-1}(1-\frac{1}{n})$ and $b_n=P_n^{-1}(1)$. By the monotonicity of $P_n^{-1}$ we have $a_n<b_n$ for each $n$. Note that:

(a) $\displaystyle x_n<x_{n+1} \Leftrightarrow x_n>1-\frac{1}{n} \Leftrightarrow P_n^{-1}(x_n)>P_n^{-1}(1-\frac{1}{n}) \Leftrightarrow x_1>a_n$; (b) $\displaystyle x_n<1 \Leftrightarrow P_n^{-1}(x_n)<P_n^{-1}(1) \Leftrightarrow x_1<b_n$.

Thus, $0<x_n<x_{n+1}<1,\forall n$ holds if and only if $a_n<x_1<b_n,\forall n$, or $\displaystyle x_1 \in \bigcap_{n=1}^{+\infty}(a_n,b_n)$. We need to show that $\displaystyle \bigcap_{n=1}^{+\infty}(a_n,b_n)$ is a singleton. We have:

(c) if $x_1=a_n$, then $x_n=1-\frac{1}{n}$, which implies that $x_{n+1}=1-\frac{1}{n}<1-\frac{1}{n+1}=P_{n+1}(a_{n+1})$, and $x_1<a_{n+1}$. It follows that $a_n<a_{n+1},\forall n$; and (d) if $x_1=b_n$, then $x_n=1$, which implies that $x_{n+1}=1+\frac{1}{n}>1=P_{n+1}(b_{n+1})$, and $x_1>b_{n+1}$. It follows that $b_n>b_{n+1},\forall n$; and

Thus, $a_n<a_{n+1}<b_{n+1}<b_n, \forall n$. Therefore, the two sequences $\{a_n\}_{n=1}^{+\infty}$ and $\{b_n\}_{n=1}^{+\infty}$ converge, and their limits $a$ and $b$ satisfy $a \leq b$. Hence, $\displaystyle \bigcap_{n=1}^{+\infty}(a_n,b_n)=[a,b]$ is non-empty, which demonstrates the existence of $x_1$.

Now, suppose that $a \leq x_1 \leq x_1' \leq b$. We have $x_{n+1}'-x_{n+1} = (x_n'-x_n)(x_n'+x_n+\frac{1}{n}) \geq (x_n'-x_n)(2-\frac{1}{n}) \geq (x_n'-x_n)$ for each $n$, so that $x_n'-x_n \geq x_1'-x_1$ for each $n$. However, $1-\frac{1}{n}<x_n \leq x_n'<1$, so that $0 \leq x_n'-x_n<\frac{1}{n}$, which implies that $\displaystyle \lim_{n \rightarrow +\infty}(x_n'-x_n)=0$. Therefore, $x_1' \leq x_1$, proving unicity.

This solution was posted and copyrighted by DAFR. The original thread for this problem can be found here: [1]

Solution 2

For each $n \ge 1$ let $I_n$ be the interval of real numbers $0 \textless x \textless 1$ such that if $x=x_1$, we will have $x_n \textless x_{n+1} \textless 1$. (That is, the values of $x_1$ which make $x_{n+1}$ "work"). We must prove these intervals intersect at one point.

First, I prove they intersect. Notice that as $x_1$ increases, $x_n$ and $x_{n+1}$ do too. So if $I_n=(a_n,b_n)$ it is easy to see $a_n=x_1$ will give $x_n=x_{n+1}=1-1/n$ and $b_n=x_1$ will give $x_{n+1}=1$ (the "extremal" values $x_{n+1}$ can take are given by the extremal values $x_1$ can take).

But if $a_n=x_1$ we see that $x_{n+1} \textless 1-1/(n+1)$ and so $x_{n+1} \textgreater x_{n+2}$ and similarly $x_1=b_n$ gives $x_{n+1}=1$ which gives a $x_{n+2}$ too big. So basically when $x_1$ only barely works for $x_{n+1}$, it won't work for $x_{n+2}$. So $I_{n+1}$ is a subset of $I_n$.

So we have an infinite sequence of open intervals, each contained inside the previous one. Therefore their intersection must contain at least one number. This guarantees the existence of $x_1$.

But, we must prove that $x_1$ can't take two different values. Suppose it could. Suppose $x_1=a,b$ both work. Let $x_i$ be the sequence generated by $a$ and $x_i'$ the sequence generated by $b$, and let $l_i=x_i'-x_i$ (wlog $a \textless b$). Then we see $l_{n+1}=l_n(2x_n+l_n+1/n) \textgreater l_n$ for $n \ge 2$ since $2x_n \textgreater 1$ since $x_n \textgreater 1-1/n \ge 1/2$. So there exists a constant $C$ such that $x_k' \ge x_k+C$ for $k \ge 2$. But since $x_k, x_k' \in (1-1/k, 1)$, this is impossible. So we're done.

This solution was posted and copyrighted by JuanOrtiz. The original thread for this problem can be found here: [2]

Solution 3

Consider, now, the following observations:

(a) If, at any point, $x_{n+1}\le x_n$, then from here we know that \[x_n\le 1-\frac{1}{n},\quad x_{n+1}\le 1-\frac{1}{n} < 1-\frac{1}{n+1}\to x_{n+2}<x_{n+1}, \cdots x_m\le 1-\frac{1}{n} < 1-\frac{1}{m}\to x_{m+1}<x_m, \forall m>n\]and therefore the sequence $\{x_n\}$ will be monotonically decreasing after one point.

(b) If some $x$ does satisfy $0<x_n<x_{n+1}<1$ for all $n$, then $1-\frac{1}{n}<x_n<1$ for all $n$, and therefore by Squeeze's theorem $\lim_{n\to\infty}x_n = 1$.

(c) If $x_n\ge 1$ for some $n$, then $x_{n+1}=x_n(x_n+\frac 1n)>x_n^2\ge 1$ and so $x_{n+m}>(x_{m+1})^{2^{m-1}}$ which then gives $\lim_{n\to\infty}x_n=+\infty$.

(d) If $x_1=0$, then for each $n$, $x_n=0$. If $x_1\to\infty$ then for each $n$ (fixed), $x_n\to\infty$. Thus, we can denote a mapping $f_n:\mathbb{R}^{\ge 0}\to \mathbb{R}^{\ge 0}$ that maps $x_1$ to $x_n$, which is continuous and monotonically increasing, with $\lim_{x\to +\infty} f_n(x)=+\infty$ so $f_n$ is bijective.

Let's first show uniqueness. Suppose that $\{x_n\}$ and $\{y_n\}$ are both such sequences. We have $\lim_{n\to\infty}x_n=\lim_{n\to\infty}y_n=1$ and suppose that $y_1>x_1$. Then for all $n$, \[\frac{y_{n+1}}{x_{n+1}} = \frac{y_n(y_n+\frac 1n)}{x_n(x_n+\frac 1n)}>\frac{y_n}{x_n}\] so inductively, $\frac{y_{n+1}}{x_{n+1}}>(\frac{y_{1}}{x_{1}})^n$ with $\lim_{n\to\infty}\frac{y_{n+1}}{x_{n+1}}=+\infty$. However, $\lim_{n\to\infty}x_n=\lim_{n\to\infty}y_n=1$ gives $\lim_{n\to\infty}\frac{y_{n+1}}{x_{n+1}}=\frac{1}{1}=1$, contradiction. Hence, the $x_1$ that satisfies this must be unique.

Next, let's show existence. We have seen from above that, $y_1>x_1$ implies $y_n>x_n$, and that if $x_n>1$ for some $n$ then $\{x_n\}$ is monotonically increasing after some point. Suppose no such $x_1$ exists. Let \[ A=\{x_1: \exists n: x_{n+1}<x_n\}\qquad B=\{x_1: \exists n: x_n>1\} \]then if $x\in A$, $y\in A$ for all $y<x$ and similarly $x\in B$, $y\in B$ for all $y>B$. Notice also an wasy fact that $1\in B$, so $A$ is bounded. Define, now, $c=glb(A)$. As we assumed $A\cup B=\mathbb{R}^+$, this $c$ implies that $x_1<c\to x_1\in A$ and $x_1>c\to x_1\in B$. It remains to ask whether $c\in A$ or $c\in B$.

If $c\in A$, then for this $x_1:=c$, $x_n\le 1-\frac{1}{n}$ and so $x_{n+1}<1-\frac{1}{n+1}$. Let $y_{n+1}$ be such that $x_{n+1}<y_{n+1}<1$. By above, there's exactly one $y_1$ with $f_{n+1}(y_1)<y_{n+1}$, and notice that $y_1>x_1=c$ by the monotonicity of $f_{n+1}$. This means that there exists $y_1>c\in A$, contradicting the definition of glb. A similar contradiction (but opposite direction) can also be established for the case $c\in B$.

Hence $c$ is neither in $A$ or $B$, means that $x_1=c$ should satisfy the problem condition. Q.E.D.

This solution was posted and copyrighted by Anzoteh. The original thread for this problem can be found here: [3]

See Also

1985 IMO (Problems) • Resources
Preceded by
Problem 5 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Last Question
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1985_IMO_Problems/Problem_6&oldid=144026"