Difference between revisions of "2020 CIME II Problems/Problem 9"
(→Solution) |
Anyu tsuruko (talk | contribs) |
||
Line 21: | Line 21: | ||
==Solution 2== | ==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 | ||
+ | |||
+ | ==Solution 3== | ||
+ | Given the function <math>f(x)=x^2-2</math>, we need to find the number of real numbers <math>x</math> that satisfy: | ||
+ | <cmath> | ||
+ | f^{2019}(x)=f^{2020}(x) | ||
+ | </cmath> | ||
+ | |||
+ | Here, <math>f^n(x)</math> denotes the function <math>f</math> iterated <math>n</math> times. To proceed, we note that: | ||
+ | <cmath> | ||
+ | f^{2020}(x)=f\left(f^{2019}(x)\right) | ||
+ | </cmath> | ||
+ | |||
+ | Thus, the equation becomes: | ||
+ | <cmath> | ||
+ | f^{2019}(x)=f\left(f^{2019}(x)\right) | ||
+ | </cmath> | ||
+ | |||
+ | Let <math>y=f^{2019}(x)</math>. Then we need: | ||
+ | <cmath> | ||
+ | y=f(y) | ||
+ | </cmath> | ||
+ | |||
+ | Given <math>f(y)=y^2-2</math>, the equation <math>y=y^2-2</math> can be rewritten as: | ||
+ | <cmath> | ||
+ | y^2-y-2=0 | ||
+ | </cmath> | ||
+ | |||
+ | Solving this quadratic equation: | ||
+ | <cmath> | ||
+ | y^2-y-2=(y-2)(y+1)=0 | ||
+ | </cmath> | ||
+ | |||
+ | Thus, <math>y</math> can be either 2 or -1 . Hence, we must solve for <math>x</math> such that: | ||
+ | 1. <math>f^{2019}(x)=2</math> | ||
+ | 2. <math>f^{2019}(x)=-1</math> | ||
+ | |||
+ | First, consider <math>f^{2019}(x)=2</math>. We will determine the structure of the iterates of <math>f</math> to see how many <math>x</math> lead to 2 . Next, consider <math>f^{2019}(x)=-1</math> and analyze similarly. | ||
+ | |||
+ | We start by analyzing the dynamics of <math>f(x)</math>. The fixed points of <math>f(x)</math> are the solutions to <math>x=f(x)</math> : | ||
+ | <cmath> | ||
+ | x=x^2-2 \Rightarrow x^2-x-2=0 | ||
+ | </cmath> | ||
+ | |||
+ | The solutions are <math>x=2</math> and <math>x=-1</math>. | ||
+ | |||
+ | Next, we analyze the behavior around these fixed points: | ||
+ | - For <math>y=2, f(2)=2^2-2=2</math>. So 2 is a fixed point of <math>f</math>. | ||
+ | - For <math>y=-1, f(-1)=(-1)^2-2=-1</math>. So -1 is also a fixed point of <math>f</math>. | ||
+ | |||
+ | Now we determine the number of preimages for these points under <math>f</math>. | ||
+ | Given <math>y=2</math> : | ||
+ | <cmath> | ||
+ | f(x)=2 \quad \Rightarrow \quad x^2-2=2 \quad \Rightarrow \quad x^2=4 \quad \Rightarrow \quad x= \pm 2 | ||
+ | </cmath> | ||
+ | |||
+ | Given <math>y=-1:</math> | ||
+ | <cmath> | ||
+ | f(x)=-1 \quad \Rightarrow \quad x^2-2=-1 \quad \Rightarrow \quad x^2=1 \quad \Rightarrow \quad x= \pm 1 | ||
+ | </cmath> | ||
+ | |||
+ | At each iteration, each of <math>\pm 2</math> and <math>\pm 1</math> can have 2 preimages under the iteration. This means the total number of solutions doubles with each iteration. | ||
+ | - For <math>f^{2019}(x)=2</math>, starting with 2, it could be reached through <math>f^{2018}(x)= \pm 2</math> with doubling at each iteration. | ||
+ | - For <math>f^{2019}(x)=-1</math>, starting with -1 , it could be reached through <math>f^{2018}(x)= \pm 1</math> with doubling at each iteration. | ||
+ | |||
+ | Each iteration brings doubling of the number of preimages, leading to: | ||
+ | <cmath> | ||
+ | 2^{2019} \text { for each target value }(2 \text { and }-1) | ||
+ | </cmath> | ||
+ | |||
+ | Summing these: | ||
+ | <cmath> | ||
+ | N=2 \times 2^{2019}=2^{2020} | ||
+ | </cmath> | ||
+ | |||
+ | Finally, we find the remainder when <math>2^{2020}</math> is divided by 1000 . Using Euler's theorem for finding <math>2^{2020} \bmod 1000</math> : | ||
+ | <cmath> | ||
+ | \phi(1000)=400 | ||
+ | </cmath> | ||
+ | |||
+ | Thus, | ||
+ | <cmath> | ||
+ | 2^{400} \equiv 1 \quad \bmod 1000 | ||
+ | </cmath> | ||
+ | |||
+ | Since <math>2020=5 \times 400+20</math> | ||
+ | <cmath> | ||
+ | 2^{2020}=\left(2^{400}\right)^5 \cdot 2^{20} \equiv 1^5 \cdot 2^{20} \equiv 2^{20} \quad \bmod 1000 | ||
+ | </cmath> | ||
+ | |||
+ | Computing <math>2^{20} \bmod 1000</math> : | ||
+ | <cmath> | ||
+ | 2^{10}=1024 \Rightarrow 1024 \quad \bmod 1000=24 \ | ||
+ | 2^{20}= \left(2^{10}\right)^2=24^2=576 | ||
+ | </cmath> | ||
+ | |||
+ | Thus, the remainder when <math>N</math> is divided by 1000 is: | ||
+ | |||
+ | By AnYu |
Latest revision as of 02:48, 23 May 2024
Contents
[hide]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
Solution 3
Given the function , we need to find the number of real numbers that satisfy:
Here, denotes the function iterated times. To proceed, we note that:
Thus, the equation becomes:
Let . Then we need:
Given , the equation can be rewritten as:
Solving this quadratic equation:
Thus, can be either 2 or -1 . Hence, we must solve for such that: 1. 2.
First, consider . We will determine the structure of the iterates of to see how many lead to 2 . Next, consider and analyze similarly.
We start by analyzing the dynamics of . The fixed points of are the solutions to :
The solutions are and .
Next, we analyze the behavior around these fixed points: - For . So 2 is a fixed point of . - For . So -1 is also a fixed point of .
Now we determine the number of preimages for these points under . Given :
Given
At each iteration, each of and can have 2 preimages under the iteration. This means the total number of solutions doubles with each iteration. - For , starting with 2, it could be reached through with doubling at each iteration. - For , starting with -1 , it could be reached through with doubling at each iteration.
Each iteration brings doubling of the number of preimages, leading to:
Summing these:
Finally, we find the remainder when is divided by 1000 . Using Euler's theorem for finding :
Thus,
Since
Computing :
Thus, the remainder when is divided by 1000 is: