Problem A. 861. (October 2023)

A. 861. Let \(\displaystyle f(x)=x^2-2\). Let \(\displaystyle f^{(n)}(x)\) denote the \(\displaystyle n^{\text{th}}\) iterate of \(\displaystyle f\) (i.e. \(\displaystyle f^{(1)}(x)=f(x)\) and \(\displaystyle f^{(k+1)}(x)=f\big(f^{(k)}(x)\big)\)).

Let \(\displaystyle H=\big\{x\colon f^{(100)}(x)\le -1\big\}\). Find the length of \(\displaystyle H\) (the sum of the lengths of the intervals in \(\displaystyle H\)). We expect the solution as a closed-form expression.

Submitted by Dávid Matolcsi, Budapest

(7 pont)

Deadline expired on November 10, 2023.

If \(\displaystyle |x|>2\), then \(\displaystyle x^2-2>2\), thus all the iterated values will be bigger than 2, and so \(\displaystyle f^{(100)}(x)>2>-1\).

If \(\displaystyle |x|\le 2\), then it is easy to check that \(\displaystyle |x^2-2|\le 2\), and so all the iterated values will be between -2 and 2.

With \(\displaystyle y(x)=\frac{x+2}{4}\) we can transform \(\displaystyle x\) to be between 0 and 1. Also, \(\displaystyle y(f(x))=\frac{x^2}{4}=(2y(x)-1)^2\), and \(\displaystyle x\le -1\) is equivalent to \(\displaystyle y\le\frac{1}{4}\).

With these steps we rephrased the problem as finding the total length of the intervals where \(\displaystyle g^{(n)}(y)\in [0,\frac{1}{4}]\) for \(\displaystyle g(y)=(2y-1)^2\).

Let \(\displaystyle \alpha(y)=\arccos{(\sqrt{y})}\). Clearly \(\displaystyle \alpha(y)\in [0,\frac{\pi}{2}]\), and \(\displaystyle y=\cos^2(\alpha)\) and \(\displaystyle g(y)=\cos^2(2\alpha)\). This immediately gives \(\displaystyle g^{(n)}(y)=\cos^2(2^n \alpha)\).

\(\displaystyle g^{(n)}(y)\in [0,c]\) is equivalent to \(\displaystyle 2^n\alpha\in [r,\pi-r]\) mod \(\displaystyle \pi\), where \(\displaystyle r=\arccos{\sqrt{c}}\), and this means

\(\displaystyle \alpha\in \left[\frac{r}{2^n}, \frac{\pi-r}{2^n}\right]\cup \left[\frac{\pi+r}{2^n}, \frac{2\pi-r}{2^n}\right]\cup ... \cup \left[\frac{(2^{n-1}-1)\pi+r}{2^n}, \frac{2^{n-1}\pi-r}{2^n}\right].\)

Translating this to \(\displaystyle y\) we get

\(\displaystyle y\in \left[\cos^2(\frac{\pi-r}{2^n}), \cos^2(\frac{r}{2^n})\right]\cup \left[\cos^2(\frac{2\pi-r}{2^n}), \cos^2(\frac{\pi+r}{2^n})\right]\cup ... \cup \left[\cos^2(\frac{2^{n-1}\pi-r}{2^n}), \cos^2(\frac{(2^{n-1}-1)\pi+r}{2^n})\right].\)

Using identity \(\displaystyle \cos^2\alpha=\frac{1}{2}(1+\cos(2\alpha))\) and summation formula

\(\displaystyle \cos(a)+\cos(a+d)+...+\cos(a+(m-1)d)=\frac{\sin\left(\frac{md}{2}\right)\cos\left(a+\frac{(m-1)d}{2}\right)}{\sin\left(\frac{d}{2}\right)}\)

with \(\displaystyle a=\frac{r}{2^{n-1}}\) and \(\displaystyle \frac{\pi-r}{2^{n-1}}\), \(\displaystyle d=\frac{\pi}{2^{n-1}}\), \(\displaystyle m=2^{n-1}\), we get that this sum is

\(\displaystyle \frac{1}{2}\frac{\sin(\frac{\pi}{2})}{\sin(\frac{\pi}{2^n})}\left(\cos(\frac{\pi}{2}-\frac{\pi}{2^n}+\frac{2r}{2^n})-\cos(\frac{\pi}{2}+\frac{\pi}{2^n}-\frac{2r}{2^n})\right)=\frac{\sin\left(\frac{\pi-2r}{2^n}\right)}{\sin\left(\frac{\pi}{2^n}\right)}.\)

Since \(\displaystyle x=4y-2\), every interval for \(\displaystyle y\) corresponds to an interval four times as long for \(\displaystyle x\). In our problem \(\displaystyle n=100\) and \(\displaystyle r=\arccos{\sqrt{\frac{1}{4}}}=\frac{\pi}{3}\), and thus the answer to our problem is

\(\displaystyle \frac{4\sin\left(\frac{\pi}{3\cdot 2^{100}}\right)}{\sin\left(\frac{\pi}{2^{100}}\right)}.\)

Since for small values \(\displaystyle \sin x\) can be approximated with \(\displaystyle x\), this value is very close to \(\displaystyle \frac{4}{3}\).

—–

Imagine that on the interval \(\displaystyle [-2,2]\), a value \(\displaystyle x_1\) represents the true state of a particle. We measure it, but commit an inevitable measurement error of the magnitude \(\displaystyle 2^{-20}\), and start our calculations with the obtained value \(\displaystyle x_2\). Then, as it is clear from the proof, approximately after the \(\displaystyle 20^{\text{th}}\) iteration, the value calculated from \(\displaystyle x_2\) tells us nothing about where the actual \(\displaystyle x_1\) particle is in the \(\displaystyle 20^{\text{th}}\) iteration.

This is a classic example of chaos theory: it is impossible to model the process accurately over the long term, as the smallest measurement errors at the starting state can completely distort the result. It is said that the laws describing the operation of weather work in a similar way, which is why it is impossible to predict the weather beyond a few weeks. The famous saying is more or less true: ``If a butterfly flaps its wings in New York, it can cause a typhoon in Shanghai a month later.´´

Statistics:

13 students sent a solution.
7 points:	Fekete Aron, Varga Boldizsár, Zömbik Barnabás.
6 points:	Diaconescu Tashi.
3 points:	1 student.
0 point:	8 students.

Problems in Mathematics of KöMaL, October 2023