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"

(Created page with "For every real number <math>x_1</math>, construct the sequence <math>x_1,x_2,\ldots</math> by setting <math>x_{n+1}=x_n \left(x_n + \frac{1}{n}\right)</math> for each <math>n \ge...")
 
Line 1: Line 1:
 +
==Problem==
 
For every real number <math>x_1</math>, construct the sequence <math>x_1,x_2,\ldots</math> by setting <math>x_{n+1}=x_n \left(x_n + \frac{1}{n}\right)</math> for each <math>n \geq 1</math>.  Prove that there exists exactly one value of <math>x_1</math> for which <math>0<x_n<x_{n+1}<1</math> for every <math>n</math>.
 
For every real number <math>x_1</math>, construct the sequence <math>x_1,x_2,\ldots</math> by setting <math>x_{n+1}=x_n \left(x_n + \frac{1}{n}\right)</math> for each <math>n \geq 1</math>.  Prove that there exists exactly one value of <math>x_1</math> for which <math>0<x_n<x_{n+1}<1</math> for every <math>n</math>.
 +
 +
==Solution 1==
 +
By recursive substitution, one can write <math>x_n=P_n(x_1)</math> , where <math>P_n</math> is a polynomial with non-negative coefficients and zero constant term. Thus, <math>P_n(0)=0</math>, <math>P_n</math> is strictly increasing in <math>[0,+\infty)</math> , and <math>\displaystyle \lim_{x_1 \rightarrow + \infty} P_n(x_1)=+\infty</math>. We can therefore define the inverse <math>P_n^{-1}</math> of <math>P_n</math> on <math>[0,+\infty)</math>. It follows that <math>x_1=P_n^{-1}(x_n)</math>, <math>P_n^{-1}(0)=0</math>, <math>P_n^{-1}</math> is strictly increasing in <math>[0,+\infty)</math>, and <math>\displaystyle \lim_{x_1 \rightarrow + \infty} P_n^{-1}(x_1) =+\infty</math>.
 +
 +
Denote by <math>\displaystyle a_n=P_n^{-1}(1-\frac{1}{n})</math> and <math>b_n=P_n^{-1}(1)</math>. By the monotonicity of <math>P_n^{-1}</math> we have <math>a_n<b_n</math> for each <math>n</math>. Note that:
 +
 +
(a) <math>\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</math>;
 +
(b) <math>\displaystyle x_n<1 \Leftrightarrow P_n^{-1}(x_n)<P_n^{-1}(1) \Leftrightarrow x_1<b_n</math>.
 +
 +
Thus, <math>0<x_n<x_{n+1}<1,\forall n</math> holds if and only if <math>a_n<x_1<b_n,\forall n</math>, or <math>\displaystyle x_1 \in \bigcap_{n=1}^{+\infty}(a_n,b_n)</math>. We need to show that <math>\displaystyle \bigcap_{n=1}^{+\infty}(a_n,b_n)</math> is a singleton. We have:
 +
 +
(c) if <math>x_1=a_n</math>, then <math>x_n=1-\frac{1}{n}</math>, which implies that <math>x_{n+1}=1-\frac{1}{n}<1-\frac{1}{n+1}=P_{n+1}(a_{n+1})</math>, and <math>x_1<a_{n+1}</math>. It follows that <math>a_n<a_{n+1},\forall n</math>; and
 +
(d) if <math>x_1=b_n</math>, then <math>x_n=1</math>, which implies that <math>x_{n+1}=1+\frac{1}{n}>1=P_{n+1}(b_{n+1})</math>, and <math>x_1>b_{n+1}</math>. It follows that <math>b_n>b_{n+1},\forall n</math>; and
 +
 +
Thus, <math>a_n<a_{n+1}<b_{n+1}<b_n, \forall n</math>. Therefore, the two sequences <math>\{a_n\}_{n=1}^{+\infty}</math> and <math>\{b_n\}_{n=1}^{+\infty}</math> converge, and their limits <math>a</math> and <math>b</math> satisfy <math>a \leq b</math>. Hence, <math>\displaystyle \bigcap_{n=1}^{+\infty}(a_n,b_n)=[a,b]</math> is non-empty, which demonstrates the existence of <math>x_1</math>.
 +
 +
Now, suppose that <math>a \leq x_1 \leq x_1' \leq b</math>. We have <math>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)</math> for each <math>n</math>, so that <math>x_n'-x_n \geq x_1'-x_1</math> for each <math>n</math>. However, <math>1-\frac{1}{n}<x_n \leq x_n'<1</math>, so that <math>0 \leq x_n'-x_n<\frac{1}{n}</math>, which implies that <math>\displaystyle \lim_{n \rightarrow +\infty}(x_n'-x_n)=0</math>. Therefore, <math>x_1' \leq x_1</math>, proving unicity.
 +
 +
This solution was posted and copyrighted by DAFR. The original thread for this problem can be found here: [https://aops.com/community/p2751173]
 +
 +
==Solution 2==
 +
For each <math>n \ge 1</math> let <math>I_n</math> be the interval of real numbers <math>0 \textless x \textless 1</math> such that if <math>x=x_1</math>, we will have <math>x_n \textless x_{n+1} \textless 1</math>. (That is, the values of <math>x_1</math> which make <math>x_{n+1}</math> "work"). We must prove these intervals intersect at one point.
 +
 +
First, I prove they intersect. Notice that as <math>x_1</math> increases, <math>x_n</math> and <math>x_{n+1}</math> do too. So if <math>I_n=(a_n,b_n)</math> it is easy to see <math>a_n=x_1</math> will give <math>x_n=x_{n+1}=1-1/n</math> and <math>b_n=x_1</math> will give <math>x_{n+1}=1</math> (the "extremal" values <math>x_{n+1}</math> can take are given by the extremal values <math>x_1</math> can take).
 +
 +
But if <math>a_n=x_1</math> we see that <math>x_{n+1} \textless 1-1/(n+1)</math> and so <math>x_{n+1} \textgreater x_{n+2}</math> and similarly <math>x_1=b_n</math> gives <math>x_{n+1}=1</math> which gives a <math>x_{n+2}</math> too big. So basically when <math>x_1</math> only barely works for <math>x_{n+1}</math>, it won't work for <math>x_{n+2}</math>. So <math>I_{n+1}</math> is a subset of <math>I_n</math>.
 +
 +
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 <math>x_1</math>.
 +
 +
But, we must prove that <math>x_1</math> can't take two different values. Suppose it could. Suppose <math>x_1=a,b</math> both work. Let <math>x_i</math> be the sequence generated by <math>a</math> and <math>x_i'</math> the sequence generated by <math>b</math>, and let <math>l_i=x_i'-x_i</math> (wlog <math>a \textless b</math>). Then we see <math>l_{n+1}=l_n(2x_n+l_n+1/n) \textgreater l_n</math> for <math>n \ge 2</math> since <math>2x_n \textgreater 1</math> since <math>x_n \textgreater 1-1/n \ge 1/2</math>. So there exists a constant <math>C</math> such that <math>x_k' \ge x_k+C</math> for <math>k \ge 2</math>. But since <math>x_k, x_k' \in (1-1/k, 1)</math>, 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: [https://aops.com/community/p3492644]
 +
 +
==Solution 3==
 +
Consider, now, the following observations:
 +
 +
(a) If, at any point, <math>x_{n+1}\le x_n</math>, then from here we know that
 +
<cmath>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</cmath>and therefore the sequence <math>\{x_n\}</math> will be monotonically decreasing after one point.
 +
 +
(b) If some <math>x</math> does satisfy <math>0<x_n<x_{n+1}<1</math> for all <math>n</math>, then <math>1-\frac{1}{n}<x_n<1</math> for all <math>n</math>, and therefore by Squeeze's theorem <math>\lim_{n\to\infty}x_n = 1</math>.
 +
 +
(c) If <math>x_n\ge 1</math> for some <math>n</math>, then <math>x_{n+1}=x_n(x_n+\frac 1n)>x_n^2\ge 1</math> and so <math>x_{n+m}>(x_{m+1})^{2^{m-1}}</math> which then gives <math>\lim_{n\to\infty}x_n=+\infty</math>.
 +
 +
(d) If <math>x_1=0</math>, then for each <math>n</math>, <math>x_n=0</math>. If <math>x_1\to\infty</math> then for each <math>n</math> (fixed), <math>x_n\to\infty</math>. Thus, we can denote a mapping <math>f_n:\mathbb{R}^{\ge 0}\to \mathbb{R}^{\ge 0}</math> that maps <math>x_1</math> to <math>x_n</math>, which is continuous and monotonically increasing, with <math>\lim_{x\to +\infty} f_n(x)=+\infty</math> so <math>f_n</math> is bijective.
 +
 +
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>,
 +
\[
 +
\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.
 +
Hence, the <math>x_1</math> that satisfies this must be unique.
 +
 +
Next, let's show existence. We have seen from above that, <math>y_1>x_1</math> implies <math>y_n>x_n</math>, and that if <math>x_n>1</math> for some <math>n</math> then <math>\{x_n\}</math> is monotonically increasing after some point. Suppose no such <math>x_1</math> exists. Let
 +
\[
 +
A=\{x_1: \exists n: x_{n+1}<x_n\}\qquad B=\{x_1: \exists n: x_n>1\}
 +
\]then if <math>x\in A</math>, <math>y\in A</math> for all <math>y<x</math> and similarly <math>x\in B</math>, <math>y\in B</math> for all <math>y>B</math>. Notice also an wasy fact that <math>1\in B</math>, so <math>A</math> is bounded. Define, now, <math>c=glb(A)</math>. As we assumed <math>A\cup B=\mathbb{R}^+</math>, this <math>c</math> implies that <math>x_1<c\to x_1\in A</math> and <math>x_1>c\to x_1\in B</math>. It remains to ask whether <math>c\in A</math> or <math>c\in B</math>.
 +
 +
If <math>c\in A</math>, then for this <math>x_1:=c</math>, <math>x_n\le 1-\frac{1}{n}</math> and so <math>x_{n+1}<1-\frac{1}{n+1}</math>. Let <math>y_{n+1}</math> be such that <math>x_{n+1}<y_{n+1}<1</math>. By above, there's exactly one <math>y_1</math> with <math>f_{n+1}(y_1)<y_{n+1}</math>, and notice that <math>y_1>x_1=c</math> by the monotonicity of <math>f_{n+1}</math>. This means that there exists <math>y_1>c\in A</math>, contradicting the definition of glb. A similar contradiction (but opposite direction) can also be established for the case <math>c\in B</math>.
 +
 +
Hence <math>c</math> is neither in <math>A</math> or <math>B</math>, means that <math>x_1=c</math> 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: [https://aops.com/community/p18824436]
 +
 +
== See Also == {{IMO box|year=1985|num-b=5|after=Last Question}}

Revision as of 23:01, 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=144025"