2020 CIME II Problems/Problem 9

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

Page

Toolbox

Search

2020 CIME II Problems/Problem 9

Problem 9

Solution 1

Solution 2