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 == | ||
− | {{ | + | 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 == | ||
− | {{ | + | 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 16:19, 28 July 2015
Problem
Let and
for
Prove that for any positive integer n the roots of the equation
are all real and distinct.
Solution
I shall prove by induction that has
distinct real solutions, where
are positive and
are negative. Also, for ever root
,
.
Clearly, 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 ,
has
distinct real solutions with absolute values less than 2, where
are positive and
are negative.
Choose a root of
. Let
, where
is a real root of
. We have that
, so
, so
is real and
. Therefore all of the roots of
are real and have absolute values less than 2.
Note that the function is an even function, since
is an even function. Therefore half of the roots of
are positive, and half are negative.
Now assume for the sake of contradiction that has a double root
. Let
. Then there exists exactly one real number
such that
. The only way that this could happen is when
, or
. However,
from our inductive hypothesis, so this is a contradiction. Therefore
has no double roots. This proves that that the roots of
are distinct.
This completes the inductive step, which completes the inductive proof.
Alternate Solution
Let . We then have that
, and we can prove using induction that
. Thus, we just need to solve
, which happens when
or
. These give that
or
. As we can choose the range
to ensure no duplications, we get that, upon rearranging,
and
. There are
integers in the first range and
in the second. However, exactly one time, they product the same
:
. Thus, there are
distinct roots for
. We can also prove using induction that there are
roots of
. Thus, all roots of
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 |