Hello! In fact,we want to prove that $\exists n\in \mathbb{N}$ such that $a_n< \frac{1}{2}\leq b_n$,or,more generally,such that $\frac{1}{\sqrt[2^m]{2}}\leq a_n<\frac{1}{\sqrt[2^{m+1}]{2}}\leq b_n$. (This happens because $a_n<\frac{1}{2}\Leftrightarrow a_{n+1}>a_{n}$ and $a_{n}\geq \frac{1}{2}\Leftrightarrow a_{n+1}<a_n$). Suppose that the above is not true.Then,for all $i\in \mathbb{N}$,if $a_{i}\in A=\left[\frac{1}{\sqrt[2^m]{2}},\frac{1}{\sqrt[2^{m+1}]{2}}\right)$,then $b_{i}\in A$ We can suppose that $\frac{1}{\sqrt{2}}>a,b\geq \frac{1}{2}$ $\rule{430pt}{1pt}$ We can make this assumption because of the following reason: If $a,b$ are "big" (close to $1$) then,with successive applications of $f$ they will become small enough (since $|x|<1\Rightarrow \lim_{n\to +\infty} x^n=0$) so as to be smaller than $\frac{1}{\sqrt{2}}$.More specifically,if $a_{i}\in A$ then $a_{i+m}\in K=\left[\frac{1}{2},\frac{1}{\sqrt{2}}\right)$. If $a,b$ are "small" then,they become "big" in the first step and then they become smaller just as in the previous case. In both cases we can begin counting from the point when $a_{i},b_{i} \in K$. $\rule{430pt}{1pt}$ Back to our problem,suppose that $d_n=a_n-b_n$.This difference doens't change when we apply the upper part of $f$ and it doesn't decrease when we apply the lower part of $f$.We shall show that this difference will become very big. Thus it is non-decreasing. (we want it to become greater that $\frac{1}{2}$ in order to raise the contradiction). Obviously $d_1=(b-a)(b+a)$ and $d_2=d_1$.Also $d_3=b_3-a_3=b_2^2-a_2^2=(b_2-a_2)(b_2+a_2)=$ $=(b-a)(b+a)(b_1+a_1+1)=(b-a)(b+a)(b^2+a^2+1)$ We have $(b+a)(b^2+a^2+1)>\frac{3}{2}$. Thus every time we have $a_{j},b_{j}\in K$ we also have $d_{j}> \frac{3d_{j-k}}{2}$ where $a_{j-k},b_{j-k}\in K$ and there doesn't exist $l$ with $j-k<l<j$ with $a_{l},b_{l}\in K$ (This is because $d_n$ is non-decreasing and $d_{j+2}>\frac{3d_j}{2}$ for all $j$ with the above property). Since the procedure is repeated infinitely many times,and due to the fact that it is a repetition of what we described inside the black lines, there will be infinitely many $k$ with the property $a_{k},b_{k}\in K$. Since $\lim_{n\to +\infty} \left(\frac{3}{2}\right)^n=+\infty$ the sequence $d_n$ will eventually become greater than $\frac{1}{2}$, which raises the contradiction.

Suppose, on the contrary, that $(a_n-a_{n-1})(b_n-b_{n-1}) \geq 0$ for all $n\in \mathbb{N}$. Then, $a_n \geq a_{n-1}$ and $b_n \geq b_{n-1}$ or $a_n \leq a_{n-1}$ and $b_n \leq b_{n-1}$. It is easy to prove that $a_{n-1}<\frac{1}{2}$ and $b_{n-1}<\frac{1}{2}$ or $a_{n-1}\geq\frac{1}{2}$ and $b_{n-1}\geq\frac{1}{2}$. Lemma 1: $a_n \geq \frac{1}{2}$ for infinitely many $n$. Proof: Just note that if $a_n < \frac{1}{2}$, then $a_{n+1} \geq \frac{1}{2}$. Lemma 2: $a_n \geq \frac{3}{4}$ and $b_n \geq \frac{3}{4}$ are both true for infinitely many $n$. Proof: Use lemma 1 and our initial assumption. Lemma 3: Let $g(n)=b_n-a_n$. Then, $g(n)>\frac{1}{2}$ for some $n$. Proof: Note that either $g(n) \geq g(n-1)$ or $g(n) \geq \frac{3}{2} g(n-1)$, depending on which side of $\frac{1}{2}$ $a_n$ and $b_n$ are on. Use lemma 2 to show that there exists a $k$ such that $g(k) \geq (\frac{3}{2})^{\lceil log_\frac{3}{2} \frac{1}{2g(1)} \rceil} g(1) > \frac{1}{2}$. We get a contradiction to our initial assumption since $a_n$ and $b_n$ are on the same side of $\frac{1}{2}$ and are between 0 and 1. Thus, the problem is proved.

Suppose that the conclusion is false, and let $g(n)=b_n-a_n$. If $a_i,b_i<\dfrac{1}{2}$, we have $$g(i+1)=b_{i+1}-a_{i+1}=\left (b_i+\dfrac{1}{2} \right )-\left ( a_i+\dfrac{1}{2} \right )= g(i)$$ If $a_i,b_i\ge \dfrac{1}{2}$, we have $$g(i+1)=b_i^2-a_i^2=(b_i-a_i)(b_i+a_i)=g(i)(b_i-a_i+2a_i)\ge g(i)(g(i)+1)\ge g(i)(g(0)+1)$$

we have that for any $n\in \mathbb{N}$, we find $k$ such that $g(k)\ge g(0)(g(0)+1)^n$. As $g(0)(g(0)+1)^n$ grows unboundedly, we have reached a contradiction.

The problem is equivalent to showing that at some step we must have $a_n \ge \frac{1}{2},b_n < \frac{1}{2}$.Wlog let $a,b>\frac{1}{2}$. If there exist $k$ such that $\frac{1}{2^{\frac{1}{2^k}}} \le a < \frac{1}{2^{\frac{1}{2^{k+1}}}}$ and $b \ge \frac{1}{2^{\frac{1}{2^{k+1}}}}$ then we are through as $a_{k+1}=a^{2^{k+1}}<\frac{1}{2}$ and $b_{k+1}>\frac{1}{2}$. We now assume that $\frac{1}{2} \le a,b <\frac{1}{\sqrt{2}}$.Let $d_i=a_i-b_i$.Note that $d_2=b^2-a^2$ and $d_3=d_2,d_4=(a^2+\frac{1}{2})^2-(b^2+\frac{1}{2})^2=a^4-b^4+a^2-b^2=d_1(a+b)(a^2+b^2+1) \ge \frac{3d_1}{2}$. We define the set $S=\{(a_i,b_i):\frac{1}{2} \le a_i < b_i <\frac{1}{\sqrt{2}} \}$.If for a $k$ we have $\frac{1}{2^{\frac{1}{2^k}}} \le a < b < \frac{1}{2^{\frac{1}{2^{k+1}}}}$ and if at any step we have $j$ such that $\frac{1}{2^{\frac{1}{2^j}}} \le a_i < \frac{1}{2^{\frac{1}{2^{j+1}}}}$ and $b_i \ge \frac{1}{2^{\frac{1}{2^{j+1}}}}$ then we are through.Otherwise we eventully arrive at a member of $S$,say $a_n,b_n$.Now note that $d_{n+3} \ge \frac{3d_n}{2}$ by previous para.After that we again start finding the $a_i$'s till another member of $S$ is found otherwise we are through midway.If we are do not get any $a_i,b_i$ which can be seperated intervally as in the first para then we will have $d_n>1$ for some $n$ which is absurd.

Assume for a contradiction that such a positive integer $n$ does not exist. Note that $f(x) > x \iff x\in \left (0, \frac{1}{2}\right )$ and $f(x) < x \iff x\in \left [\frac{1}{2}, 1\right )$, so it must be the case that $a_i, b_i \in \left (0, \frac{1}{2}\right )$ or $a_i, b_i\in \left [\frac{1}{2}, 1\right )$ for all $i\geq 0$. In particular, if we let $L$ and $R$ denote the intervals $\left (0,\frac{1}{2}\right )$ and $\left [\frac{1}{2}, 1\right )$, respectively, and let the itinerary of $c\in (0,1)$ be the sequence $S_0S_1S_2\cdots$ where $S_i=L \iff f^i(c)\in L$, then $a$ and $b$ must have the same itinerary. We observe that after an $L$ we must have an $R$. Let $d_i = b_i - a_i$ for $i\geq 0$. If $a_i\in L$, then $d_{i+1} = d_i$. If $a_i\in R$, then $d_{i+1} = b_i^2-a_i^2 = (b_i-a_i)(b_i+a_i)\geq b_i-a_i=d_i$, as $a_i, b_i\geq \frac{1}{2}$. Thus $d_i$ is an increasing sequence. Now consider the itinerary for $a$ and take the last $R$ in a block of $R$'s; let this correspond to $a_k$. Then $a_k, b_k \in \left [\frac{1}{2}, \frac{1}{\sqrt{2}} \right )$ so $a_{k+1}, b_{k+1}\in \left [\frac{1}{4}, \frac{1}{2} \right )$ and $a_{k+2}, b_{k+2} \geq \frac{3}{4}$. Thus $d_{k+3} = b_{k+2}^2 - a_{k+2}^2 = (b_{k+2}+a_{k+2})(b_{k+2}-a_{k+2}) \geq \frac{3}{2} d_{k+2}$. Since no sequence of $R$'s can be infinite, there are infinitely many blocks of $R$ and infinitely many increases by a factor of $\frac{3}{2}$. So we have a contradiction as the $a_i$ and $b_i$ are confined in $(0, 1)$.

Suppose on the contrary that $(a_n-a_{n-1})(b_n-b_{n-1}) > 0$ for all $n\ge 1$ (clearly it cannot equal zero since $f$ has no fixed points). Since if $a_k < \dfrac{1}{2}\implies a_{k+1} > \dfrac{1}{2} > a_k$ and $a_k > \dfrac{1}{2}\implies a_{k+1}=a_k^2 < a_k$, then it follows that $a_n < \dfrac{1}{2} \iff b_n < \dfrac{1}{2} \quad (*)$. Let $b_n-a_n=\varepsilon_n$. Then if $a_k<\dfrac{1}{2}$, then $a_{k+1} = a_k+\dfrac{1}{2}$ and $b_{k+1} = b_k+\dfrac{1}{2}+\varepsilon_k\implies \varepsilon_{k+1}=\varepsilon_k$. Otherwise $a_k > \dfrac{1}{2}$ so $a_{k+1}=a_k^2$ and $b_{k+1}=b_k^2 = (a_k+\varepsilon_k)^2=a_k^2+2a_k\varepsilon_k+\varepsilon_k^2\implies \varepsilon_{k+1} = 2a_k\varepsilon_k+\varepsilon_k^2 > \varepsilon_k+\varepsilon_k^2$. since $a_k>\dfrac{1}{2}\implies 2a_k > 1$. This means $\{\varepsilon_k\}$ is a non-decreasing sequence. Since $a_k > \dfrac{1}{2}$ infinitely many times, $\{\varepsilon_k\}$ increases infinitely many times. Define $g(n)=n+n^2$. It remains to prove that there exists an $i$ such that $g^i(\varepsilon_0) > \dfrac{1}{2}$, because that would contradict $(*)$. But by an easy induction, we see $g^i(n) \ge n+in^2$ so $\lim\limits_{i\to \infty} g^i(n) = \infty$, done. $\Box$

This problem was proposed by Asbjørn Nordentoft, Denmark.

Call the interval $[\frac{1}{2}, 1)$ the upper side and the interval $(0, \frac{1}{2})$ the lower side. Notice that the problem is equivalent to showing there exists $i$ such that $a_i$ and $b_i$ are on different sides, as if a number x is on the upper side $f(x)-x<0$ and if x is on the lower side $f(x)-x>0$. Now, assume for the sake of contradiction there exists numbers $a$ and $b$ such that $a_i$ and $b_i$ always stay on the same side. Assume wlog that $a>b$ and let $a_i-b_i=k_i$. First, note that for $i>0$, $a_i>\frac{1}{4}$ and likewise for $b_i$. This is true because the range of $f$ is $[\frac{1}{4}, 1)$. Next, we prove that there are infinite $i$ such that $a_i$ and $b_i$ are on the lower side. Assume otherwise, this means that there is an infinite string in $a_i$ for which it stays on the upper side. This is impossible as $x^{2^h}$ always tends to $0$ as $h$ goes to infinity when $x\in(0, 1)$. Done. Now, notice that $k_i$ is non-decreasing as either $k_{i+1}=\left(a_i+\frac{1}{2}\right)-\left(a_i+\frac{1}{2}\right)=k_i$ or $k_{i+1}=a_i^2-b_i^2=(a_i+b_i)k_i$ which is greater than $k_i$ since $a_i, b_i>\frac{1}{2}$. Choose a number $j$ such that $a_j$ and $b_j$ are on the lower side. Then, we have $a_{j+1}, b_{j+1}\ge \frac{3}{4}$, which means $$k_{j+1}=(a_{j+1}+b_{j+1})k_j\ge \frac{3}{2}k_j$$ Thus, since $\left(\frac{3}{2}\right)^x$ is unbounded, $k_0>0$, and $a_i$ and $b_i$ are on the lower side infinitely times, there must exist an index $c$ such that $k_c>\frac{1}{2}$, which implies that $a_c$ and $b_c$ are on different sides, a contradiction. $\blacksquare$

Assume FTSOC that $(a_n-a_{n-1})(b_n-b_{n-1})>0$ for all $n$ (note that it cannot be 0 since we can never have two consecutive terms of the sequences the same). This means $a_n>a_{n-1}$ and $b_n>b_{n-1}$ for all $n$, or $a_n<a_{n-1}$ and $b_n<b_{n-1}$ for all $n$. Note that if $x<1/2$, then $f(x)>x$, and if $x\ge 1/2$, then $f(x)<x$. So if $a_n>a_{n-1}$ and $b_n>b_{n-1}$, then we must have $a_n>1/2$ and $b_n>1/2$, and in the other case, we must have $a_n\le 1/2$ and $b_n \le 1/2$. Therefore, ($a_n,b_n < 1/2$ or $a_n,b_n \ge 1/2$) for all $n$. Let $d_n=b_n-a_n$. Note that $|d_n| < 1$ since $a_n,b_n \in (0,1)$. Case 1: $a_n,b_n < 1/2$. Then \[ d_{n+1} = b_{n+1}-a_{n+1} = (b_n+1/2)-(a_n+1/2) = b_n-a_n = d_n. \] Case 2: $a_n,b_n \ge 1/2$. Then \begin{align*} d_{n+1} &= b_{n+1}-a_{n+1} \\ &= b_n^2-a_n^2 \\ &= (b_n-a_n)(b_n+a_n) \\ &\ge (b_n-a_n)(b_n+(1-a_n)) \text{ since }a_n\ge 1/2 \\ &= (b_n-a_n)(1+(b_n-a_n))\\ &= d_n(1+d_n). \end{align*}Therefore, $d_{n+1} = d_n$ or $d_{n+1} \ge d_n(1+d_n)$ for all $n$. But if $d_{n+1}=d_n$, then $a_n,b_n < 1/2$, so then $a_{n+1},b_{n+1} >1/2$, so we land in case 2. Therefore, we land in case 2 infinitely many times. We now claim that $\{d_n\}$ is unbounded, which will provide a contradiction, since $|d_n|<1$. We have $d_{n+1} \ge d_n+d_n^2$. Let $d_0=b-a=\varepsilon$. We claim $d_n \ge \varepsilon + n\varepsilon^2$. Induct on $n$. For $n=0$, it is true by definition. Then, \[ d_{n+1} \ge d_n+d_n^2 = (\varepsilon+n\varepsilon^2) + (\varepsilon+n\varepsilon^2)^2 > \varepsilon + (n+1)\varepsilon^2. \]Therefore, $d_n$ can grow arbitrarily large, which is a contradiction. $\blacksquare$

EDIT: just saw that this solution is essentially the same as bobthesmartypants, though I came up with it independently. darn.

Suppose not. Then for all $n \geq 0$, $a_n$ and $b_n$ lie on the same side of $\frac{1}{2}$. Note that $f(x) \geq \frac{1}{4}$ which it acquires for $x=\frac{1}{2}$. Let $s_n=b_n-a_n$, which is positive since $f$ is a strictly increasing function and $b_0>a_0$. Then we have $$\text{If } a_n,b_n<\frac{1}{2} \text{, then } s_{n+1}=\left(b_n+\frac{1}{2} \right)-\left(a_n+\frac{1}{2} \right)=s_n$$$$\text{AND}$$$$\text{If } a_n,b_n \geq \frac{1}{2} \text{, then } s_{n+1}=b_n^2-a_n^2=s_n(a_n+b_n) \geq s_n$$In particular, this gives that $(s_n)_{n \geq 0}$ is a non-decreasing sequence. Now, consider some $n \in \mathbb{N}$ for which $a_{n-1},b_{n-1}<\frac{1}{2}$. Clearly, there are infinitely many such $n$. Also, we get $$a_{n-1},b_{n-1} \geq \frac{1}{4} \Rightarrow a_n,b_n \geq \frac{3}{4} \Rightarrow s_n \leq \frac{1}{4}$$But this means that $$s_{n+1}=s_n(a_n+b_n) \geq \frac{3}{2}s_n \text{ for infinitely many } n$$Since, $s_n$ is non-decreasing, so we can say that for all $k \in \mathbb{N}$, there exists a sufficiently large $M$ with $s_M \geq \left(\frac{3}{2} \right)^ks_0$. But, as shown above, we have $s_n \leq \frac{1}{4}$ for infinitely many $n$, which combined with the fact that $s_n$ is strictly increasing gives that $s_n \leq \frac{1}{4}$ for every $n \in \mathbb{N}$. Then taking $k$ really large in the previous inequality gives a contradiction. $\blacksquare$

Solved with pinetree1. Suppose for sake of contradiction that $(a_n-a_{n-1})(b_n-b_{n-1})>0$ always. This means that at every step, $a_n$ and $b_n$ are both in the same interval from the set $\{(0,1/2),[1/2,1)\}$. Note that $a_n-b_n$ is weakly increasing, this being clear if $a_n,b_n<1/2$ and clear if $a_n,b_n\ge 1/2$ since $a_{n+1}-b_{n+1}=(a_n-b_n)(a_n+b_n)$ and $a_n+b_n\ge 1$. Consider $n$ such that $a_n\ge 1/2$ but $a_{n+1}<1/2$. Clearly this happens infinitely often. We see that $a_{n+1}\ge 1/4$, so $a_{n+2}\ge 3/4$. Similarly $b_{n+2}\ge 3/4$, so \[a_{n+3}-b_{n+3}\ge \frac{3}{2}(a_{n+2}-b_{n+2}) \ge \frac{3}{2}(a_n-b_n).\]Since this occurs infinitely often, $a_n-b_n$ grows too big, which is the desired contradiction.

Solved with nukelauncher. Assume for contradiction that for all \(n\), \(a_n>a_{n-1}\) if and only if \(b_n>b_{n-1}\). Note that if \(x<\frac12\), then \(f(x)>\frac12>x\), and if \(s\ge\frac12\), then \(f(x)<x\); hence, \(a_n<\frac12\) if and only if \(b_n<\frac12\). Now let \(c_n=b_n-a_n\). If \(a_n,b_n<\frac12\), then \(c_{n+1}=(b_n+\frac12)-(a_n+\frac12)=c_n\), and if \(a_n,b_n\ge\frac12\), then \[c_{n+1}=(a_n+c_n)^2-a_n^2=c_n(2a_n+c_n)>c_n(1+c_n).\] Recall that \(a_n,b_n<\frac12\) imply \(a_{n+1},b_{n+1}\ge\frac12\), so for all values of \(n\), independent of the values of \(a_n\) and \(b_n\), we have \[c_{n+2}>c_n(1+c_n)\ge c_n(1+c_1).\]It follows that for \(n\) large, \(c_n\ge\frac12\), which is absurd.

Solution from Twitch Solves ISL: Note that $f$ has no fixed points. Assume for contradiction $a < b$ do not have this property. Call an index $i$ up if $a_{i+1} > a_i$ and $b_{i+1} > b_i$, else a down index. It's clear there are infinitely many up indices. Now let $d_n = |b_n - a_n|$. Claim: We have If $d_n$ is a down index, then $d_{n+1} = d_n$. If $d_n$ is an up index, then $d_{n+1} \ge d_n + (b-a)^2$. Proof. The first case is obvious. For the other case, note that \begin{align*} d_{n+1} &= \left\lvert b_n^2 - a_n^2 \right\rvert = \left\lvert b_n + a_n \right\rvert \cdot \left\lvert b_n - a_n \right\rvert \\ &\ge \left( \frac{1}{2} + \left( \frac{1}{2} + d_n \right) \right) \cdot d_n \\ &\ge d_n + (b-a)^2. \end{align*}$\blacksquare$ On the other hand, we obviously have $d_n < 1$ for all $n$. Since there are infinitely many up indices, the previous claim gives a contradiction.

Assume FTSOC that it never happens that either ($a_n<\frac12$ and $b_n\geq \frac12$) or vice versa. (Note that if this does happen then $a_{n+1}-a_n>0$ as well as $b_{n+1}-b_n<0$, which finishes) Note $b_0>a_0$. Let $c_n= b_n-a_n$. Now, claim $c_n$ is non-decreasing. If they both increase by $\frac12$, this is true. Otherwise, note that when $a_n,b_n\geq \frac12$, then if they drop below $\frac12$, then $a_{n+1},b_{n+1}\geq \frac14$, so then, $a_{n+2},b_{n+2}\geq \frac34$. Thus, for $k=n+2$, then \[c_{k+1} = b_k^2-a_k^2 = (b_k-a_k)\cdot (b_k+a_k) \geq \frac32 b_n-a_n = \frac32 c_n\]Thus, $c_n$ goes up by a factor of $\frac32$ infinitely often, and since $c_0>0$, at some point $c_M>\frac12$, contradiction and we are done.

Let the $x + \frac{1}{2}$s be called Inc(short for increment), and the others called Dec(short for decrease). Observe that two consecutive Incs is never possible. Assume the opposite of the hypothesis; then we find that the Decs or Incs for both $a$ and $b$ are always the same. The assumption that Decs or Incs are the exact same for both $a$ and $b$ implies that $a_i < b_i$ holds for any $i$. Consider the sequence defined by $d_i = b_i - a_i$. The key claim is: Claim: The sequence $(d_i)$ is nondecreasing and is never eventually constant. Consider $d_i = b_i - a_i$ and $d_{i + 1} = b_{i + 1} - a_{i + 1}$. If an Inc happens, then of course $d_{i + 1} = d_i$ but Incs can't happen consecutively, yielding the second half of the claim. If a Dec happens, then we know that \begin{align*} b_{i + 1} - a_{i + 1} &= b_i^2 - a_i^2 \\ &= (a_i + d_i)^2 - a_i^2 \\ &= 2a_i \cdot d_i + d_i^2 \\ &\geq d_i + d_i^2, \end{align*}where the last part is because $2a_i \geq 1$. $\square$ In fact, if the initial difference is $d_1$, then we know that anytime we do a Dec, the difference increases by at least $d_1^2$. Thus by taking large $n$ we find that the difference between $b_n$ and $a_n$ exceeds $\frac{1}{2}$, which is a contradiction.

$|a_n-b_n|=|a_{n-1}-b_{n-1}|(a_{n-1}+b_{n-1})$ if they are both above $\frac{1}{2}$ and remains constant otherwise. Every time right after both $a,b$ depart from $(0,\frac{1}{2})$, their sum will be greater than $1.5$, hence their difference does grow arbitrarily large and they will be in different intervals.

Assume otherwise. We claim that the difference $b_n-a_n$ is nondecreasing. Note that if $a_{n-1}, b_{n-1} < \frac 12$, then $$a_n - b_n = a_{n-1} - b_{n-1},$$and if $a_{n-1}, b_{n-1}$ are both greater than $\frac 12$, then $\frac 14 < a_n, b_n \implies \frac 34 < a_{n+1}, b_{n+1}$. Then $$a_{n+2} - b_{n+2} = (a_{n+1} - b_{n+1})(a_{n+1}+b_{n+1}) > \frac 32 (a_{n+1} - b_{n+1}).$$If $a_{n-1} < \frac 12 \leq b_{n-1}$ or vice versa, we have the desired result. This means that unless $a_n < \frac 12 \leq b_n$ for some $n$, then for sufficiently large $n$ the difference will increase by $\frac 32$ infinitely many times, so we will have $a_n - b_n > \frac 12$, which forces the conclusion to be true, as required.

Assume FTSOC that $a_{n+1}>a_n\iff b_{n+1}>b_n$ for all $n$. Note that $|b_n-a_n|$ is a weakly increasing sequence, since if $a_n,b_n\in (0,1/2)$, then go up by $1/2$, so no change to the difference, and if $a_n,b_n\in [1/2,\infty)$, then both square, then $b_{n+1}-a_{n+1}=b_n^2-a_n^2=(b_n-a_n)(b_n+a_n)>b_n-a_n$. Let $A_0=(0,1/2)$ and $A_i=[1/2^{1/2^{i-1}}, 1/2^{1/2^i})$ for each $i\ge 1$. The interval $(0,1)$ can be split as $A_0\sqcup A_1 \sqcup \cdots$, i.e. \[ \left(0,\frac{1}{2^1}\right), \left(\frac{1}{2^{1}},\frac{1}{2^{1/2}}\right), \left(\frac{1}{2^{1/2}},\frac{1}{2^{1/4}}\right), \left(\frac{1}{2^{1/4}},\frac{1}{2^{1/8}}\right), \ldots\]Under $f$, note the following facts: For any $i\ge 1$, a value in $A_i$ will go to a value in $A_{i-1}$, since it will square. A value in $A_0$ will go a value in some $A_i$ for some $i\ge 1$, since it will increase by $1/2$. (An example of the indices of the $A$-sets that a chain of $f$'s follow is: $0\to 2\to 1 \to 0 \to 3 \to 2 \to 1 \to 0 \to 4 \to \cdots$.) Lemma: $a_i$ and $b_i$ are in the same $A$-set, for all $i$. Proof: The key thing to realize is that two numbers $x,y > 1/2$ will take the same number of steps to come back down to $A_0$ if and only if $x,y$ are in the same $A$-set. Since we are assuming that after each kick out from $A_0$ the two sequences $(a_i)$ and $(b_i)$ take the same number of steps to come back to $A_0$, this means $a_i,b_i$ are in the same $A$-set for all $i$. A corollary is that $|b_i-a_i| \le 1/2$ for all $i$. $\blacksquare$ Claim: $a_n\in A_2$ for infinitely many $n$, i.e. in the chain, $2$ is hit infinitely many times. Proof: Due to how the $A$-indices of the chain of $f$'s works, it suffices to show that the chain is not $0\to 1\to 0\to 1\to 0 \to 1 \to \cdots$. Assume FTSOC this was the chain. Then for some $a\in A_1=(1/2,1/\sqrt2)$, we would have $a\to a^2\to a^2+1/2$, so $a^2+1/2 \in A_1$. But \[a^2+\frac12 > \left(\frac12\right)^2+\frac12 = \frac34 > \frac{1}{\sqrt2},\]contradiction. $\blacksquare$ From the Claim, we have $a_n\in A_2$ for infinitely many $n$. For these $n$, we have $b_n\not \in A_0$ since $a_n>1/2$, so $b_n\ge 1/2$. Then \[ |b_{n+1}-a_{n+1}|=|b_n^2-a_n^2|=|b_n-a_n|\cdot (b_n+a_n) \ge |b_n-a_n|\cdot \left( \frac12 + \frac{1}{\sqrt2}\right). \]Noe $1/2+1/\sqrt2 \approx 1.207>1$. So for infinitely many $n$, the sequence $|b_i-a_i|$ multiplies by $>1.207$, and this sequence is also nondecreasing, so combining these implies it is unbounded. This contradicts $|b_i-a_i|\le 1/2$ for all $i$.

For the sake of simplicity of this proof, let "above" mean $\ge\frac12$ and let "below" mean $<\frac12$. Note that $f(x)-x$ is negative iff $x\ge\frac12$. Therefore, we want one of $a_{n-1},b_{n-1}$ to be above and one to be below. Assume FTSOC that this cannot happen. This means that the sequences $a$ and $b$ synchronously go above and below. Note that eventually, you will go from above to below, and below clearly goes to above in one step. Therefore, let $c_n=b_n-a_n$. This is clearly positive(given our assumption), gets multiplied by $b_n+a_n$ which is $\ge1$ every time they are above, and doesn't change every time they are below, meaning that it is a nondecreasing sequence. However, note that whenever you go from below to above, you are at at least $\left(\frac12\right)^2+\frac12=\frac34$, so $c_n$ gets multiplied by $\frac34+\frac34=\frac32$ whenever you go from below to above, which happens an infinite number of times throughout the infinite sequence. Therefore, $c_n$ goes to infinity, which is impossible as its unreachable maximum is $1-0=1$, contradiction, and therefore, QED.

Suppose that $a_n$ and $b_n$ are always either both less than $\frac{1}{2}$ or both at least $\frac{1}{2}.$ Then, consider $d_n=b_n-a_n.$ If both are less than $\frac{1}{2}$ then $d_{n+1}=d_{n}.$ If both are at least $\frac{1}{2}$, $d_{n+1}=(b_n-a_n)(b_n+a_n)$ so we can see that $b_n$ stays greater than $a_n$, and furthermore, $b_n+a_n=2a_n+d_n> 1$ so $d_n$ is strictly increasing if $a_n,b_n\ge \frac{1}{2}.$ Since whenever $a_n,b_n< \frac{1}{2}$ we have $a_{n+1},b_{n+1}\ge \frac{1}{2}$, we see that $d_{n+2}\ge d_n(2a_{n+1}+d_n)\ge d_n(1+d_n).$ It is easy to see that this gets arbitrarily large, which is a contradiction. Let $a_n< \frac{1}{2},b_n\ge \frac{1}{2}$ then $b_{n+1}-b_n$ is negative where $a_{n+1}-a{n}$ is positive, so we're done.

Assume otherwise. Notice the sequence $a_n, b_n$ always behaves identically. Then notice $b - a$ nonzero, weakly increasing and bounded above. Hence it has a limit. However, this is a contradiction as if its limit is $d > 0$ then the next time it increases it becomes at least $b^2-a^2 \geq d + d^2 > d$ where $d^2$ is positive and basically constant with respect to the limit, so we are done.

Define a sequence $\{x_n\}$ such that $x_1=x<1$ and $x_n=f(x_{n-1})$. Claim: ${x_n}$ cannot be strictly increasing nor strictly decreasing Proof: We will prove this by cases, ) If $x<\frac{1}{2}$, then, \begin{align*} x_2=x+\frac{1}{2} >x \implies x_3=\left(x+\frac{1}{2}\right)^2=x_2^2 \end{align*}Since $x_2<1$, we have $x_3<x_2$. So the sequence is not strictly increasing. It is obvious that, there will exist an $x_i$ such that \begin{align*} x_i=\left(x+\frac{1}{2}\right)^{2^{i-2}}<\frac{1}{2} \end{align*}Then we will have $x_{i+1}=x_i+\frac{1}{2} >x_i$. Thus this sequence is not strictly decreasing. ) If $x\leq \frac{1}{2}$, then \begin{align*} x_2=x^2<x \end{align*}Now there will exist an $x_i$ such that $x_i=x^{2^i}<\frac{1}{2}$, so $x_{i+1}=x_i+\frac{1}{2} >x_i$. Thus this sequence is not strictly decreasing nor strictly increasing.$\blacksquare$ Thus, $\{a_n\}$ and $\{b_n\}$ are not strictly increasing nor strictly decreasing. Claim: $b_i>a_i$ for $i\in \mathbb{Z}^+$ Proof: We have $b>a$, and since the operations "adding a $\frac{1}{2}$" and "squaring" doesn't affect the bounding, we have $b_i>a_i$ for all $i\in \mathbb{Z}^+$.$\blacksquare$ Since $b_i>a_i$ and the sequence has arbitrary increasing and decreasing points, we have $k\in \mathbb{Z}^+$ such that $a_k<\frac{1}{2}$ and $b_k>\frac{1}{2}$. Thus, \begin{align*} a_{k+1}=a_k+\frac{1}{2}>a_k \quad \& \quad b_{k+1}=b_k^2<b_k \end{align*}Thus we have $(b_{k+1}-b_{k})(a_{k+1}-a_k)<0$.

View the sequence as a process, where we apply the function once to our current terms $a_i$ and $b_i$ each second. Call a move an up move if we go from $(a_i,b_i)$ to $(a_i+\tfrac{1}{2},b_i+\tfrac{1}{2})$, and a down move if we go from $(a_i,b_i)$ to $(a_i^2,b_i^2)$. If there does not exist a positive integer $n$ with $(a_n-a_{n-1})(b_n-b_{n-1})<0$, then every move is either an up or down move. Call a block of moves a circle if it starts with an up move, followed by a series of down moves, and is then followed by but does not contain an up move. For example, $(0,\tfrac{1}{5}) \to (\tfrac{1}{2},\tfrac{7}{10}) \to (\tfrac{1}{4},\tfrac{49}{100})$ is a circle. Evidently there are infinitely many circles (we cannot apply two up moves in a row, and if we apply a down move sufficiently many times the terms eventually go below $\tfrac{1}{2}$). Define $d_i:=b_i-a_i$, so $d_0=b-a>0$. In an up move, the difference won't change, while in a down move we go from $b_i-a_i=d_i$ to $b_i^2-a_i^2=(b_i-a_i)(b_i+a_i)$. Since if we down move from $(a_i,b_i)$ we have $a_i,b_i\geq \tfrac{1}{2}$, we have $b_i+a_i\geq 1$ and the sequence $d_n$ is nondecreasing. Moreover, if we have some circle starting at $k$, we have $d_{k+1}=d_k$ and $d_{k+2}=d_k(1+a_k+b_k)$. Since $b_k=a_k+d_k>d_k$, it follows that $d_{k+2}\geq d_k(1+d_k)\geq d_k(1+d_0)$, so by the time the cycle ends with last term $l-1$ we have $d_l\geq d_k(1+d_0)$ as well. Thus if $m$ is a large integer such that $N$ complete circles have occurred before $m$, we have $$d_m\geq d_0(1+d_0)^N,$$but by taking $m$ large enough so that $N$ is large enough, we get $d_m>1$, which contradicts the fact that $a_m,b_m \in (0,1)$. $\blacksquare$

NTistrulove wrote:

I do not think this solution makes sense. In particular, how does the existence of $k$ with $a_k<\tfrac{1}{2}$ and $b_k>\tfrac{1}{2}$ follow? It doesn't seem like the actual recurrence relation is used past the $b_i>a_i$ property and the non-monotonicity of the sequences, but the sequences with $a_n=\tfrac{1}{4},b_n=\tfrac{1}{3}$ for $n$ odd and $a_n=\tfrac{2}{3},b_n=\tfrac{3}{4}$ for $n$ even are non-monotonic, and $b_i>a_i$ is always true, but such a $k$ does not exist.

This is equivalent to showing there is some $n$ such that $a_n$ and $b_n$ lay on opposite sides of $\frac 12.$ Assume for the sake of contradiction there isn't. Then, consider $g(n)=(a_n-b_n)^2.$ As for all $n$ $a_n,b_n$ lie on the side made of $\frac12,$ we have either \[g(n+1)=(a_{n+1}-b_{n+1})^2=(a_n+0.5-b_n-0.5)=g(n)\]if $a_n+b_n<1$ or if $a_n+b_n\geq 1$ we have \[g(n+1)=(a_{n+1}-b_{n+1})^2=(a_n^2-b_n^2)^2=(a_n-b_n)^2(a_n+b_n)^2=(a_n+b_n)^2g(n)\geq g(n).\]Now, let $k_1,k_2,\dots$ be the indices where $a_{k_i}+b_{k_i}<1.$ From $i\geq2$, note that \[a_{k_i}+b_{k_i}\geq 2\cdot(0.5)^2=\frac 12 \iff a_{k_i+1}+b_{k_i+1}=0.5+a_{k_i}+0.5+b_{k_i}\geq 1.5\]as the previous values must have been greater than or equal to $\frac 12.$ Thus we find that $g(k_i+1)=g(k_i)$ and also that \[g(k_i+2)=g(k_i+1)(a_{k_i+1}+b_{k_i+1})\geq 2.25 g(k_i+1)=2.25g(k_i).\]But as \[g(k_{i+1})\geq g(k_{i+1}-1)\geq \dots \geq g(k_i+2)\geq 2.25g(k_i).\]Thus we find that for all $n$ we must have $g(k_{n})\geq 2.25^{n-2}g(k_2).$ But as $g(k_2)$ is a positive real number, there exists an $n$ such that $g(k_n)>0.25.$ But this in turn means $|a_{k_n}-b_{k_n}|>0.5$ which is a contradiction! Nice problem I didn’t need to do squares since I didn’t read b>a oops

Notice when $a_{k-1}<\tfrac{1}{2}$ we have $a_n-a_{n-1}>0$ and when $a_{k-1}\ge\tfrac{1}{2}$ we have $a_n-a_{n-1}<0$. Hence, it suffices to show that for some $n$ that $a_n<\tfrac{1}{2}$ and $b_n\ge\tfrac{1}{2}$ or vice versa. FTSOC assume no such $n$ exists. Notice we always have $b_n>a_n$ since the same operation (either both adding or both squaring) is always being applied to both $a$ and $b$. For $n\ge m+1$ such that $a_{n-1}$ and $b_{n-1}$ are both at least $\tfrac{1}{2}$, we claim that $b_n-a_n\ge b_{n-1}-a_{n-1}+(b_m-a_m)^2$ where $m$ is the first index where $a_m,b_m\ge \tfrac{1}{2}$. Indeed, \begin{align*}b_n-a_n&=b_{n-1}^2-a_{n-1}^2\\&=(b_{n-1}-a_{n-1})(b_{n-1}-a_{n-1}+2b_{n-1})\\&\ge b_{n-1}-a_{n-1}+(b_{n-1}-a_{n-1})^2\\&=b_{n-1}-a_{n-1}+(b_m-a_m)^2\end{align*}where the last inequality comes from the fact that $b_n-a_n$ can only increase or stay the same depending on if $a_n$ and $b_n$ are less than or at least $\tfrac{1}{2}$. Notice there are infinite values of $n$ that satisfy the above condition because whenever $a_n<\tfrac{1}{2}$, we have $a_{n+1}\ge \tfrac{1}{2}$. Hence, eventually, $b_n-a_n$ will exceed $1$, which is absurd. $\square$

Notice that the required result is identical to $a_n$ and $b_n$ being on either side of $\frac{1}{2}$. If it is so for $a_n,b_n$ for some $n\geq 1$ we are done, so assume it is not so. If $a_n<b_n<\frac{1}{2}$, we add $\frac{1}{2}$ to get them above, so WLOG assume $\frac{1}{2}<a_n<b_n<1$. Now notice that if $a_n<\frac{1}{\sqrt{2}}$ and $b_n \geq \frac{1}{\sqrt{2}}$, then squaring will give the required condition assume it is not so. The squaring operation will reduce $a_i$,$b_i$, but increase their gap.Notice that $$b^2-a^2 > b-a \Longleftrightarrow b>a > 0$$Thus, as we have a strictly increasing value for $b_n-a_n$. When $a_i$, $b_i$, drop below half, each will be added half, and so their gap will not change. Thus, overall their gap is strictly increasing. So, at some point $b_n-a_n \geq \frac{1}{\sqrt{2}}$. At this point if $\frac{1}{2}\leq a<b<\frac{1}{\sqrt{2}}$, then $a_n$,$b_n$, will be on either side of $\frac{1}{2}$ giving the required condition. And if $\frac{1}{\sqrt{2}} \leq a< b <1$, then $a_n$, $b_n$ will be on either side of $\frac{1}{\sqrt{2}}$ in turn again giving the required condition.

It's obvious that we only need the case of $a_0\geq\frac{1}{2}$ Let $b_0=a_0+x_0$ the means that $|b_0-a_0|=x_0$, now define $x_1,x_2....$ similarly. We also have that: $b_1=b_0^2=(a_0+x_0)^2=a_0^2+2a_0x_0+x_0^2$ Which means that $x_1=2a_0x_0+x_0^2$, since $2a_0\geq1$ this means that $2a_0x_0+x_0^2 \geq x_0+x_0^2$. Now how to finish this problem? we have that the sequence $x_i$ for all $i$ is increasing as $i$ approaches $\infty$. So we only need to show that $x_i\geq\frac{1}{2}$ for some $i$ which is an easy induction.

let $c_{x}$ represent the absolute difference between $a_{x}$ and $b_{x}$. case 1: if $a_{x}$ and $b_{x}$ are on different sides of $\frac{1}{2}$, we can then take $n=x+1$ because out of $a_{x}$ and $b_{x}$, the one larger than $\frac{1}{2}$ would become smaller (due to being squared when being less than 1), and the one smaller than $\frac{1}{2}$ would become larger (due to plus $\frac{1}{2}$) case 2: if $a_{x}$ and $b_{x}$ are both larger than or equal to $\frac{1}{2}$, we can denote $\min{a_{x}}{b_{x}}$ as $y$, and similarly denote $\max{a_{x}}{b_{x}}$ as $y+c_{x}$. taking $c_{x+1}=|a_{x+1}-b_{x+1}|$, we get that $c_{x+1}=2yc_{x}+(c_{x})^2=(2y+c_{x})(c_{x})$, and because $y \geq \frac{1}{2}$ and $c_{x}>0$, $c_{x+1} > c_{x}$. in any case, if we get any $a_{x}$ and $b_{x}$ both above $\frac{1}{2}$, we will get a larger $c_{x+1}$. this means that eventually, we will get a $c_{n}$ that is larger than $\frac{1}{2}$, meaning that $a_{x}$ and $b_{x}$ will be on different sides of $\frac{1}{2}$, fulfilling our requirement case 3: if $a_{x}$ and $b_{x}$ are both smaller than $\frac{1}{2}$, just add $\frac{1}{2}$ to both of them. this is literally the exact same thing as case 2.

Solved with heheman For the sake of contradiction, suppose that the given statement is incorrect. In other words, there exists no positive integer $n$ satisfying the condition. If at any point, we have $a_n < \frac{1}{2} \le b_n$, we have \[a_{n+1} = a_n + \frac{1}{2} > a_n \quad \text{and} \quad b_{n+1} = b_n^2 < b_n,\] a contradiction. Notice that this works the other way around too. If $a_n, b_n < \frac{1}{2}$, we have \[|a_{n+1}-b_{n+1}| = |a_n-b_n|\] If $a_n, b_n \ge \frac{1}{2}$, we have $a_{n+k}, b_{n+k}$ will eventually be greater than $\frac{3}{4}$, so \begin{align*} |a_{n+k+1}-b_{n+k+1}| &= |(a_{n+k}-b_{n+k})(a_{n+k}+b_{n+ k})| \\ &= (a_{n+k}+b_{n+k})|a_{n+k}-b_{n+k}| \\ &\ge \frac{3}{2} |a_{n+k}-b_{n+k}| \end{align*} As both of the aforementioned cases occur infinitely many times, $|a_n-b_n|$ will increase steadily until $|a_n-b_n| \ge \frac{1}{2}$, at which point either $a_n < \frac{1}{2} \le b_n$ or $b_n < \frac{1}{2} \le a_n$, a contradiction. $\square$

For the sake of contradiction, we assume that $(a_{n}-a_{n-1})(b_{n}-b_{n-1})> 0$ for every $n$. We define $x_{k}$ as the interval between $(\frac{1}{2})^{(\frac{1}{2})^{k-1}}$ and $(\frac{1}{2})^{(\frac{1}{2})^{k}}$. Note that after if $a_{k}$ is in interval $x_{i}$, then $a_{k+1}$ will be in interval $x_{i-1}$. If $a_{n}$ and $b_{n}$ are in different intervals after having been added $\frac{1}{2}$, then eventually $(a_{m}-a_{m-1})(b_{m}-b_{m-1}) < 0$. Thus, we must have that $a_{n}$ and $b_{n}$ are always in the same interval. However, this is impossible because if they are always in the same interval then, $a_{n}-b_{n}$ will always increase, which is impossible because the intervals are of finite length. Thus, we must have that there exists, $(a_{n}-a_{n-1})(b_{n}-b_{n-1}) < 0$.

Note that $f(x) > x$ if $x < \tfrac{1}{2}$, and $f(x) < x$ if $x \ge \tfrac{1}{2}$. Thus, it suffices to show that there exist $a_n$, $b_n$ such that one of them lies in $(0, \tfrac{1}{2})$ and the other lies in $[\tfrac{1}{2}, 1)$; assume ftsoc this is not true. For $i \ge 0$, denote $d_i = b_i - a_i$. Note that if $a_i, b_i < \tfrac{1}{2}$ then $d_{i + 1} = d_i$, and if $a_i, b_i \ge \tfrac{1}{2}$ we have \begin{align*} d_{i + 1} &= b_i^2 - a_i^2 \\ &= (b_i - a_i)(b_i + a_i)\\ &> d_i(2a_i + d_i)\\ &> d_i(1 + d_i). \end{align*}Since we also have $b_i + a_i > 2 \cdot \tfrac{1}{2} = 1$, we see that $d_{i + 1} > d_i$. So, by an inductive argument we can also find that $d_n > d_0(1 + d_0)^{n_0}$ for all positive integers $n$, where $n_0$ is the number of integers $1 \le i \le n$ such that $a_i, b_i \ge \tfrac{1}{2}$. But as $n$ grows arbitrarily large, so does $n_0$ (as the sequences oscillate between being greater than or equal to $\tfrac{1}{2}$ and less than $\tfrac{1}{2}$), which gives the desired contradiction.

Observe that the condition the problem is equivalent to finding a positive integer $n$ where $a_n, b_n$ lie in different intervals $\left[0, \frac{1}{2} \right), \left[\frac{1}{2}, 1 \right]$. (For brevity, whenever we refer to an interval we only talk about these two.) For the sake of contradiction, assume that for all positive integers $n$, we have $a_n$ and $b_n$ in the same interval. Since both operations of $f(x)$ preserve the condition that $a_n < b_n$, consider the difference $b_n - a_n$. If both $0 < a_n < b_n < \frac{1}{2}$, then $b_{n + 1} - a_{n + 1} = \left(b_n + \frac{1}{2} \right) - \left(a_n + \frac{1}{2} \right) = b_n - a_n$. On the other hand, if $\frac{1}{2} \le a_n < b_n < 1$ we have $b_{n + 1} - a_{n + 1} = b_n^2 - a_n^2 = (b_n - a_n)(b_n + a_n)$. But $b_n + a_n > 1$, so $b_{n + 1} - a_{n + 1} > b_n - a_n$. The latter two imply that the difference $b_n - a_n$ never decreases. Now to show it never stays the same, clearly $a_n, b_n$ will lie in $\left[\frac{1}{2}, 1 \right]$ for an infinite number of $n$, so $b_n - a_n$ is being multiplied by some positive constants greater than $1$ an infinite number of times. Therefore, a sufficiently large $n = k$ exists where $b_k - a_k > \frac{1}{2}$, but then $a_k, b_k$ lie in different intervals, contradiction. Our proof is complete.

Suppose otherwise. We prove the difference $d_n=b_n-a_n$ is unbounded, which will yield a contradiction. Call a number small if less than $\frac{1}{2}$, and large otherwise. Clearly $a_n$ is small if and only if $b_n$ is small as well. Note $b_n>a_n\implies d_n>0$ always (I motivated this part through polynomials!). Now notice if $a_n$ and $b_n$ are small then $d_{n+1}=d_n$. Otherwise, \[d_{n+1}=(a_n+b_n)d_n\ge d_n(d_n+1)\ge d_n(d_0+1)\]and since $a_n$ and $b_n$ should be large infinitely often this is a contradiction. $\blacksquare$

Super scuffed solution

storage

Also @above, I believe showing that $\{d_n\}$ is increasing is not enough. You have to show that it is unbounded.

The old techniques to divide in radicals of 2^m then mostly simple work to prove that they would lie on different intervals after certain time of operation.