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 "1976 IMO Problems/Problem 2"

(New page: == Problem == {{problem}} == Solution == {{solution}} == See also == {{IMO box|year=1976|num-b=1|num-a=3}})
 
(Added alternate solution)
 
(2 intermediate revisions by one other user not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
{{problem}}
+
Let <math>P_{1}(x) = x^{2} - 2</math> and <math>P_{j}(x) = P_{1}(P_{j - 1}(x))</math> for <math>j= 2,\ldots</math> Prove that for any positive integer n the roots of the equation <math>P_{n}(x) = x</math> are all real and distinct.
  
 
== Solution ==
 
== Solution ==
−
{{solution}}
+
I shall prove by induction that <math>P_n(x)</math> has <math>2^n</math> distinct real solutions, where <math>2^{n-1}</math> are positive and <math>2^{n-1}</math> are negative. Also, for ever root <math>r</math>, <math>|r|<2</math>.
 +
 
 +
Clearly, <math>P_1(x)</math> has 2 real solutions, where 1 is positive and 1 is negative. The absolute values of these two solutions are also both less than 2. This proves the base case.
 +
 
 +
Now assume that for some positive integer <math>k</math>, <math>P_k(x)</math> has <math>2^k</math> distinct real solutions with absolute values less than 2, where <math>2^{k-1}</math> are positive and <math>2^{k-1}</math> are negative.
 +
 
 +
Choose a root <math>r</math> of <math>P_{k+1}(x)</math>. Let <math>P_1(r)=s</math>, where <math>s</math> is a real root of <math>P_k(x)</math>. We have that <math>-2<s<2</math>, so <math>0<r^2<4</math>, so <math>r</math> is real and <math>|r|<2</math>. Therefore all of the roots of <math>P_{k+1}</math> are real and have absolute values less than 2.
 +
 
 +
Note that the function <math>P_{k+1}(x)</math> is an even function, since <math>P_1(x)</math> is an even function. Therefore half of the roots of <math>P_{k+1}</math> are positive, and half are negative.
 +
 
 +
Now assume for the sake of contradiction that <math>P_{k+1}(x)</math> has a double root <math>r</math>. Let <math>P_1(r)=s</math>. Then there exists exactly one real number <math>r</math> such that <math>r^2-2=s</math>. The only way that this could happen is when <math>s+2=0</math>, or <math>s=-2</math>. However, <math>|s|<2</math> from our inductive hypothesis, so this is a contradiction. Therefore <math>P_{k+1}(x)</math> has no double roots. This proves that that the roots of <math>P_{k+1}(x)</math> are distinct.
 +
 
 +
This completes the inductive step, which completes the inductive proof.
 +
 
 +
== Alternate Solution ==
 +
Let <math>x=2\cos\theta</math>. We then have that <math>P_1\left(x\right)=2\cos2\theta</math>, and we can prove using induction that <math>P_n\left(x\right)=2\cos2^n\theta</math>. Thus, we just need to solve <math>2\cos2^n\theta=2\cos\theta</math>, which happens when <math>\cos2^n\theta=\theta+2\pi k</math> or <math>\cos2^n\theta=-\theta+2\pi l</math>. These give that <math>\theta=\frac{2k}{2^n-1}\cdot\pi</math> or <math>\theta=\frac{2l}{2^n+1}\cdot\pi</math>. As we can choose the range <math>0\leq\theta\leq\pi</math> to ensure no duplications, we get that, upon rearranging, <math>0\leq k\leq2^{n-1}-\frac{1}{2}</math> and <math>0\leq l\leq2^{n-1}+\frac{1}{2}</math>. There are <math>2^{n-1}</math> integers in the first range and <math>2^{n-1}+1</math> in the second. However, exactly one time, they product the same <math>\theta</math>: <math>\theta=0</math>. Thus, there are <math>2^{n-1}+2^{n-1}+1-1=2^n</math> distinct roots for <math>\cos\theta=x</math>. We can also prove using induction that there are <math>2^n</math> roots of <math>P_n\left(x\right)</math>. Thus, all roots of <math>P_n\left(x\right)</math> are distinct and real.
 +
 
 +
Q.E.D.
 +
 
 
== See also ==
 
== See also ==
 
{{IMO box|year=1976|num-b=1|num-a=3}}
 
{{IMO box|year=1976|num-b=1|num-a=3}}

Latest revision as of 15:19, 28 July 2015

Problem

Let $P_{1}(x) = x^{2} - 2$ and $P_{j}(x) = P_{1}(P_{j - 1}(x))$ for $j= 2,\ldots$ Prove that for any positive integer n the roots of the equation $P_{n}(x) = x$ are all real and distinct.

Solution

I shall prove by induction that $P_n(x)$ has $2^n$ distinct real solutions, where $2^{n-1}$ are positive and $2^{n-1}$ are negative. Also, for ever root $r$, $|r|<2$.

Clearly, $P_1(x)$ has 2 real solutions, where 1 is positive and 1 is negative. The absolute values of these two solutions are also both less than 2. This proves the base case.

Now assume that for some positive integer $k$, $P_k(x)$ has $2^k$ distinct real solutions with absolute values less than 2, where $2^{k-1}$ are positive and $2^{k-1}$ are negative.

Choose a root $r$ of $P_{k+1}(x)$. Let $P_1(r)=s$, where $s$ is a real root of $P_k(x)$. We have that $-2<s<2$, so $0<r^2<4$, so $r$ is real and $|r|<2$. Therefore all of the roots of $P_{k+1}$ are real and have absolute values less than 2.

Note that the function $P_{k+1}(x)$ is an even function, since $P_1(x)$ is an even function. Therefore half of the roots of $P_{k+1}$ are positive, and half are negative.

Now assume for the sake of contradiction that $P_{k+1}(x)$ has a double root $r$. Let $P_1(r)=s$. Then there exists exactly one real number $r$ such that $r^2-2=s$. The only way that this could happen is when $s+2=0$, or $s=-2$. However, $|s|<2$ from our inductive hypothesis, so this is a contradiction. Therefore $P_{k+1}(x)$ has no double roots. This proves that that the roots of $P_{k+1}(x)$ are distinct.

This completes the inductive step, which completes the inductive proof.

Alternate Solution

Let $x=2\cos\theta$. We then have that $P_1\left(x\right)=2\cos2\theta$, and we can prove using induction that $P_n\left(x\right)=2\cos2^n\theta$. Thus, we just need to solve $2\cos2^n\theta=2\cos\theta$, which happens when $\cos2^n\theta=\theta+2\pi k$ or $\cos2^n\theta=-\theta+2\pi l$. These give that $\theta=\frac{2k}{2^n-1}\cdot\pi$ or $\theta=\frac{2l}{2^n+1}\cdot\pi$. As we can choose the range $0\leq\theta\leq\pi$ to ensure no duplications, we get that, upon rearranging, $0\leq k\leq2^{n-1}-\frac{1}{2}$ and $0\leq l\leq2^{n-1}+\frac{1}{2}$. There are $2^{n-1}$ integers in the first range and $2^{n-1}+1$ in the second. However, exactly one time, they product the same $\theta$: $\theta=0$. Thus, there are $2^{n-1}+2^{n-1}+1-1=2^n$ distinct roots for $\cos\theta=x$. We can also prove using induction that there are $2^n$ roots of $P_n\left(x\right)$. Thus, all roots of $P_n\left(x\right)$ are distinct and real.

Q.E.D.

See also

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