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 "2020 CIME II Problems/Problem 9"

(Created page with "==Solution== 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 func...")
 
 
(5 intermediate revisions by 2 users not shown)
Line 1: Line 1:
−
==Solution==
+
==Problem 9==
−
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 appeats 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. 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>
+
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 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
 +
 
 +
==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:
 +
\(\boxed{\text{576}}\)
 +
By AnYu

Latest revision as of 02:48, 23 May 2024

Problem 9

Let $f(x)=x^2-2$. There are $N$ real numbers $x$ such that \[\underbrace{f(f(\ldots f}_{2019\text{ times}}(x)\ldots))=\underbrace{f(f(\ldots f}_{2020\text{ times}}(x)\ldots)).\]Find the remainder when $N$ is divided by $1000$.

Solution 1

Let $f^n(x)$ denote the composition of $f$ with itself $n$ times. We require that $f^{2019}(x)=f^{2020}(x)$. Since

$f^{2020}(x)=f(f^{2019}(x))=(f^{2019}(x))^2-2$, we have $f^{2019}(x)=(f^{2019}(x))^2-2$. Hence

$(f^{2019}(x)+1)(f^{2019}(x)-2)=0$ so that $f^{2019}(x)\in\{-1,2\}$.


Now if $f^{n+1}(x)=k$ for some $k$, then $k=f^{n+1}(x)=f(f^{n}(x))=(f^{n}(x))^2-2$ so that

$f^{n}(x)=\pm\sqrt{k+2}$. Hence we find $f^{2018}(x)\in\{\pm1,\pm2\}$, and similarly

$f^{2017}(x)\in\{\pm\sqrt{3},\pm1,\pm2,0\}$. Note that at each step since our values for $k$ are $\geq -2$ we have

$\sqrt{k+2}$ is real; and $\pm\sqrt{k+2}$ are distinct, and also $\neq k$, except when $k=-2$. Note that every $x$ that satisfies $f^{n+1}(x)=k$ also satisfies $f^{n}(x)=\pm\sqrt{k+2}$. Since $-2$ is a value of $k$ starting with $f^{2018}$, we have for $n\leq 2018$, $f^{n}(x)$ must equal any one of $3\cdot 2^{2018-n}+1$ many values. It follows that there are $3\cdot 2^{2018}+1$ many real solutions.

By Eulers Theorem $2^{\phi(125)}=2^{100}\equiv1\mod 125$ so $2^{2000}=(2^{100})^{20}\equiv 1^{20}=1\mod 125$ and hence $2^{2003}\equiv 8\mod 1000$. Since $2^{15}=2^{10}\cdot 2^5\equiv 24\cdot 32=768\mod 1000$ we have $2^{2018}\equiv 8\cdot 768\equiv 144\mod 1000$. Hence $3\cdot 2^{2018}+1\equiv 3\cdot 144+1=433\mod 1000$. Thus the answer is 433 as desired.

Solution 2

We can start by finding the number of solution for smaller repeptitions of $f$. Notice that we can solve $f(f(x))=f(x)$ by applying the functional inverse $f^{-1}$ to both sides as you would to solve any equation: $f^{-1}(f(f(x)))=f^{-1}(f(x))\Longrightarrow f(x)=|x|$ (We put the absolute value bars because we know that taking the inverse of $f$ of both sides involves taking the square root of both sides, and $\sqrt{t^2}=|t|$). From here, it is easy to see that this equation has $4$ solutions at $\pm1$ and $\pm2$. We can also try for $f(f(f(x)))=f(f(x))$ (we will solve more methodically here): \[((x^2-2)^2-2)^2-2=(x^2-2)^2-2\] \[(x^2-2)^2-2)^2 = (x^2-2)^2\] \[(x^2-2)^2-2=|x^2-2|\] \[(x^2-2)^2-2=\pm(x^2-2)\] \[(x^2-2)^2=x^2 \textup{ OR } (x^2-2)^2=-x^2+4\]The first equation yeilds $4$ results, and the second equation yields $2$ results for a total of $6$ results. It appears that $\underbrace{f(f\cdots f}_{n\textup{ times}}(x))=\underbrace{f(f\cdots f}_{n-1\textup{ times}}(x))$ bas $2n$ real solutions, giving a total of $4040$ apparent solutions for the original equation. This makes logical sense considering that $f$ is an even polynomial with 2 roots. For a more formal proof, we consider $F_n(x)=\underbrace{f(f\cdots f}_{n\textup{ times}}(x))$. We are asked to find the number of solutions of the equation in the form $F_n(x)=F_{n-1}(x)$. Following from how we solved the first simple case, $f^{-1}(F_n(x))=f^{-1}(F_{n-1}(x)) = F_{n-1}(x)=|F_{n-2}(x)|$. Note that the absolute value branches off in rwo directions: $F_{n-1}(x)=\pm F_{n-2}(x)$. This would give a total of $2\cdot2n=4n$ real and complex solutions (we multiply by 2 because $f$ is a quadratic, which has 2 total roots). The complex roots come from the negative branches, so there are $2\cdot n=2n$ complex solutions. Therefore, there are a total of $2n$ real roots, which again gives $4040$ roots for the original question. The question asks for $\boxed{040}\equiv4040(\mod1000)<cmath></cmath>$~bhargavakanakapura

Solution 3

Given the function $f(x)=x^2-2$, we need to find the number of real numbers $x$ that satisfy: \[f^{2019}(x)=f^{2020}(x)\]

Here, $f^n(x)$ denotes the function $f$ iterated $n$ times. To proceed, we note that: \[f^{2020}(x)=f\left(f^{2019}(x)\right)\]

Thus, the equation becomes: \[f^{2019}(x)=f\left(f^{2019}(x)\right)\]

Let $y=f^{2019}(x)$. Then we need: \[y=f(y)\]

Given $f(y)=y^2-2$, the equation $y=y^2-2$ can be rewritten as: \[y^2-y-2=0\]

Solving this quadratic equation: \[y^2-y-2=(y-2)(y+1)=0\]

Thus, $y$ can be either 2 or -1 . Hence, we must solve for $x$ such that: 1. $f^{2019}(x)=2$ 2. $f^{2019}(x)=-1$

First, consider $f^{2019}(x)=2$. We will determine the structure of the iterates of $f$ to see how many $x$ lead to 2 . Next, consider $f^{2019}(x)=-1$ and analyze similarly.

We start by analyzing the dynamics of $f(x)$. The fixed points of $f(x)$ are the solutions to $x=f(x)$ : \[x=x^2-2 \Rightarrow x^2-x-2=0\]

The solutions are $x=2$ and $x=-1$.

Next, we analyze the behavior around these fixed points: - For $y=2, f(2)=2^2-2=2$. So 2 is a fixed point of $f$. - For $y=-1, f(-1)=(-1)^2-2=-1$. So -1 is also a fixed point of $f$.

Now we determine the number of preimages for these points under $f$. Given $y=2$ : \[f(x)=2 \quad \Rightarrow \quad x^2-2=2 \quad \Rightarrow \quad x^2=4 \quad \Rightarrow \quad x= \pm 2\]

Given $y=-1:$ \[f(x)=-1 \quad \Rightarrow \quad x^2-2=-1 \quad \Rightarrow \quad x^2=1 \quad \Rightarrow \quad x= \pm 1\]

At each iteration, each of $\pm 2$ and $\pm 1$ can have 2 preimages under the iteration. This means the total number of solutions doubles with each iteration. - For $f^{2019}(x)=2$, starting with 2, it could be reached through $f^{2018}(x)= \pm 2$ with doubling at each iteration. - For $f^{2019}(x)=-1$, starting with -1 , it could be reached through $f^{2018}(x)= \pm 1$ with doubling at each iteration.

Each iteration brings doubling of the number of preimages, leading to: \[2^{2019} \text { for each target value }(2 \text { and }-1)\]

Summing these: \[N=2 \times 2^{2019}=2^{2020}\]

Finally, we find the remainder when $2^{2020}$ is divided by 1000 . Using Euler's theorem for finding $2^{2020} \bmod 1000$ : \[\phi(1000)=400\]

Thus, \[2^{400} \equiv 1 \quad \bmod 1000\]

Since $2020=5 \times 400+20$ \[2^{2020}=\left(2^{400}\right)^5 \cdot 2^{20} \equiv 1^5 \cdot 2^{20} \equiv 2^{20} \quad \bmod 1000\]

Computing $2^{20} \bmod 1000$ : \[2^{10}=1024 \Rightarrow 1024 \quad \bmod 1000=24 \\ 2^{20}= \left(2^{10}\right)^2=24^2=576\]

Thus, the remainder when $N$ is divided by 1000 is: \(\boxed{\text{576}}\) By AnYu

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2020_CIME_II_Problems/Problem_9&oldid=219584"