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"

(→‎Solution)
(→‎Solution)
Line 1: Line 1:
 +
==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>.
 
==Solution==
 
==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 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 02:24, 30 November 2021

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

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

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