Difference between revisions of "2020 CIME II Problems/Problem 9"
(→Solution) |
(→Solution) |
||
Line 1: | Line 1: | ||
==Problem 9== | ==Problem 9== | ||
Let <math>f(x)=x^2-2</math>. There are <math>N</math> real numbers <math>x</math> such that <cmath>\underbrace{f(f(\ldots f}_{2019\text{ times}}(x)\ldots))=\underbrace{f(f(\ldots f}_{2020\text{ times}}(x)\ldots)).</cmath>Find the remainder when <math>N</math> is divided by <math>1000</math>. | Let <math>f(x)=x^2-2</math>. There are <math>N</math> real numbers <math>x</math> such that <cmath>\underbrace{f(f(\ldots f}_{2019\text{ times}}(x)\ldots))=\underbrace{f(f(\ldots f}_{2020\text{ times}}(x)\ldots)).</cmath>Find the remainder when <math>N</math> is divided by <math>1000</math>. | ||
− | ==Solution== | + | ==Solution 1== |
+ | Let <math>f^n(x)</math> denote the composition of <math>f</math> with itself <math>n</math> times. We require that <math>f^{2019}(x)=f^{2020}(x)</math>. Since | ||
+ | |||
+ | <math>f^{2020}(x)=f(f^{2019}(x))=(f^{2019}(x))^2-2</math>, we have <math>f^{2019}(x)=(f^{2019}(x))^2-2</math>. Hence | ||
+ | |||
+ | <math>(f^{2019}(x)+1)(f^{2019}(x)-2)=0</math> so that <math>f^{2019}(x)\in\{-1,2\}</math>. | ||
+ | |||
+ | |||
+ | Now if <math>f^{n+1}(x)=k</math> for some <math>k</math>, then <math>k=f^{n+1}(x)=f(f^{n}(x))=(f^{n}(x))^2-2</math> so that | ||
+ | |||
+ | <math>f^{n}(x)=\pm\sqrt{k+2}</math>. Hence we find <math>f^{2018}(x)\in\{\pm1,\pm2\}</math>, and similarly | ||
+ | |||
+ | <math>f^{2017}(x)\in\{\pm\sqrt{3},\pm1,\pm2,0\}</math>. Note that at each step since our values for <math>k</math> are <math>\geq -2</math> we have | ||
+ | |||
+ | <math>\sqrt{k+2}</math> is real; and <math>\pm\sqrt{k+2}</math> are distinct, and also <math>\neq k</math>, except when <math>k=-2</math>. Note that every <math>x</math> that satisfies <math>f^{n+1}(x)=k</math> also satisfies <math>f^{n}(x)=\pm\sqrt{k+2}</math>. Since <math>-2</math> is a value of <math>k</math> starting with <math>f^{2018}</math>, we have for <math>n\leq 2018</math>, <math>f^{n}(x)</math> must equal any one of <math>3\cdot 2^{2018-n}+1</math> many values. It follows that there are <math>3\cdot 2^{2018}+1</math> many real solutions. | ||
+ | |||
+ | By Eulers Theorem <math>2^{\phi(125)}=2^{100}\equiv1\mod 125</math> so <math>2^{2000}=(2^{100})^{20}\equiv 1^{20}=1\mod 125</math> and hence <math>2^{2003}\equiv 8\mod 1000</math>. Since <math>2^{15}=2^{10}\cdot 2^5\equiv 24\cdot 32=768\mod 1000</math> we have <math>2^{2018}\equiv 8\cdot 768\equiv 144\mod 1000</math>. Hence <math>3\cdot 2^{2018}+1\equiv 3\cdot 144+1=433\mod 1000</math>. Thus the answer is 433 as desired. | ||
+ | |||
+ | ==Solution 2== | ||
We can start by finding the number of solution for smaller repeptitions of <math>f</math>. Notice that we can solve <math>f(f(x))=f(x)</math> by applying the functional inverse <math>f^{-1}</math> to both sides as you would to solve any equation: <math>f^{-1}(f(f(x)))=f^{-1}(f(x))\Longrightarrow f(x)=|x|</math> (We put the absolute value bars because we know that taking the inverse of <math>f</math> of both sides involves taking the square root of both sides, and <math>\sqrt{t^2}=|t|</math>). From here, it is easy to see that this equation has <math>4</math> solutions at <math>\pm1</math> and <math>\pm2</math>. We can also try for <math>f(f(f(x)))=f(f(x))</math> (we will solve more methodically here): <cmath>((x^2-2)^2-2)^2-2=(x^2-2)^2-2</cmath> <cmath>(x^2-2)^2-2)^2 = (x^2-2)^2</cmath> <cmath>(x^2-2)^2-2=|x^2-2|</cmath> <cmath>(x^2-2)^2-2=\pm(x^2-2)</cmath> <cmath>(x^2-2)^2=x^2 \textup{ OR } (x^2-2)^2=-x^2+4</cmath>The first equation yeilds <math>4</math> results, and the second equation yields <math>2</math> results for a total of <math>6</math> results. It appears that <math>\underbrace{f(f\cdots f}_{n\textup{ times}}(x))=\underbrace{f(f\cdots f}_{n-1\textup{ times}}(x))</math> bas <math>2n</math> real solutions, giving a total of <math>4040</math> apparent solutions for the original equation. This makes logical sense considering that <math>f</math> is an even polynomial with 2 roots. For a more formal proof, we consider <math>F_n(x)=\underbrace{f(f\cdots f}_{n\textup{ times}}(x))</math>. We are asked to find the number of solutions of the equation in the form <math>F_n(x)=F_{n-1}(x)</math>. Following from how we solved the first simple case, <math>f^{-1}(F_n(x))=f^{-1}(F_{n-1}(x)) = F_{n-1}(x)=|F_{n-2}(x)|</math>. Note that the absolute value branches off in rwo directions: <math>F_{n-1}(x)=\pm F_{n-2}(x)</math>. This would give a total of <math>2\cdot2n=4n</math> real and complex solutions (we multiply by 2 because <math>f</math> is a quadratic, which has 2 total roots). The complex roots come from the negative branches, so there are <math>2\cdot n=2n</math> complex solutions. Therefore, there are a total of <math>2n</math> real roots, which again gives <math>4040</math> roots for the original question. The question asks for <math>\boxed{040}\equiv4040(\mod1000)<cmath></cmath></math>~bhargavakanakapura | We can start by finding the number of solution for smaller repeptitions of <math>f</math>. Notice that we can solve <math>f(f(x))=f(x)</math> by applying the functional inverse <math>f^{-1}</math> to both sides as you would to solve any equation: <math>f^{-1}(f(f(x)))=f^{-1}(f(x))\Longrightarrow f(x)=|x|</math> (We put the absolute value bars because we know that taking the inverse of <math>f</math> of both sides involves taking the square root of both sides, and <math>\sqrt{t^2}=|t|</math>). From here, it is easy to see that this equation has <math>4</math> solutions at <math>\pm1</math> and <math>\pm2</math>. We can also try for <math>f(f(f(x)))=f(f(x))</math> (we will solve more methodically here): <cmath>((x^2-2)^2-2)^2-2=(x^2-2)^2-2</cmath> <cmath>(x^2-2)^2-2)^2 = (x^2-2)^2</cmath> <cmath>(x^2-2)^2-2=|x^2-2|</cmath> <cmath>(x^2-2)^2-2=\pm(x^2-2)</cmath> <cmath>(x^2-2)^2=x^2 \textup{ OR } (x^2-2)^2=-x^2+4</cmath>The first equation yeilds <math>4</math> results, and the second equation yields <math>2</math> results for a total of <math>6</math> results. It appears that <math>\underbrace{f(f\cdots f}_{n\textup{ times}}(x))=\underbrace{f(f\cdots f}_{n-1\textup{ times}}(x))</math> bas <math>2n</math> real solutions, giving a total of <math>4040</math> apparent solutions for the original equation. This makes logical sense considering that <math>f</math> is an even polynomial with 2 roots. For a more formal proof, we consider <math>F_n(x)=\underbrace{f(f\cdots f}_{n\textup{ times}}(x))</math>. We are asked to find the number of solutions of the equation in the form <math>F_n(x)=F_{n-1}(x)</math>. Following from how we solved the first simple case, <math>f^{-1}(F_n(x))=f^{-1}(F_{n-1}(x)) = F_{n-1}(x)=|F_{n-2}(x)|</math>. Note that the absolute value branches off in rwo directions: <math>F_{n-1}(x)=\pm F_{n-2}(x)</math>. This would give a total of <math>2\cdot2n=4n</math> real and complex solutions (we multiply by 2 because <math>f</math> is a quadratic, which has 2 total roots). The complex roots come from the negative branches, so there are <math>2\cdot n=2n</math> complex solutions. Therefore, there are a total of <math>2n</math> real roots, which again gives <math>4040</math> roots for the original question. The question asks for <math>\boxed{040}\equiv4040(\mod1000)<cmath></cmath></math>~bhargavakanakapura |
Revision as of 08:32, 2 January 2022
Problem 9
Let . There are
real numbers
such that
Find the remainder when
is divided by
.
Solution 1
Let denote the composition of
with itself
times. We require that
. Since
, we have
. Hence
so that
.
Now if for some
, then
so that
. Hence we find
, and similarly
. Note that at each step since our values for
are
we have
is real; and
are distinct, and also
, except when
. Note that every
that satisfies
also satisfies
. Since
is a value of
starting with
, we have for
,
must equal any one of
many values. It follows that there are
many real solutions.
By Eulers Theorem so
and hence
. Since
we have
. Hence
. Thus the answer is 433 as desired.
Solution 2
We can start by finding the number of solution for smaller repeptitions of . Notice that we can solve
by applying the functional inverse
to both sides as you would to solve any equation:
(We put the absolute value bars because we know that taking the inverse of
of both sides involves taking the square root of both sides, and
). From here, it is easy to see that this equation has
solutions at
and
. We can also try for
(we will solve more methodically here):
The first equation yeilds
results, and the second equation yields
results for a total of
results. It appears that
bas
real solutions, giving a total of
apparent solutions for the original equation. This makes logical sense considering that
is an even polynomial with 2 roots. For a more formal proof, we consider
. We are asked to find the number of solutions of the equation in the form
. Following from how we solved the first simple case,
. Note that the absolute value branches off in rwo directions:
. This would give a total of
real and complex solutions (we multiply by 2 because
is a quadratic, which has 2 total roots). The complex roots come from the negative branches, so there are
complex solutions. Therefore, there are a total of
real roots, which again gives
roots for the original question. The question asks for
~bhargavakanakapura