IMO Shortlist 2014 A2

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

IMO Shortlist 2014 A2

G H J

Reveal topic tags

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

hajimbrak

209 posts

hajimbrak

#1 h Jul 11, 2015, 9:39 AM • 4 Y

Y by Davi-8191, mijail, Adventure10, Mango247

Define the function $f:(0,1)\to (0,1)$ by $\displaystyle f(x) = \left\{ \begin{array}{lr} x+\frac 12 & \text{if}\ \ x < \frac 12\\ x^2 & \text{if}\ \ x \ge \frac 12 \end{array} \right.$ Let $a$ and $b$ be two real numbers such that $0 < a < b < 1$ . We define the sequences $a_n$ and $b_n$ by $a_0 = a, b_0 = b$ , and $a_n = f( a_{n -1})$ , $b_n = f (b_{n -1} )$ for $n > 0$ . Show that there exists a positive integer $n$ such that $(a_n - a_{n-1})(b_n-b_{n-1})<0.$

Proposed by Denmark

This post has been edited 3 times. Last edited by djmathman, Jul 24, 2015, 8:08 PM
Reason: formatting

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

gavrilos

233 posts

gavrilos

#2 h Jul 11, 2015, 1:26 PM • 2 Y

Y by Adventure10, Mango247

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.

This post has been edited 1 time. Last edited by gavrilos, Jul 11, 2015, 1:26 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MathPanda1

1135 posts

MathPanda1

#3 h Jul 11, 2015, 2:30 PM • 1 Y

Y by Adventure10

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.

This post has been edited 1 time. Last edited by MathPanda1, Jul 11, 2015, 3:44 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Aiscrim

409 posts

Aiscrim

#4 h Jul 12, 2015, 10:44 AM • 16 Y

Y by ArseneLupin, Anar24, Kobayashi, Arhaan, Siddharth03, Mathematicsislovely, Illuzion, parola, hakN, Jasurbek, Adventure10, IMUKAT, Mango247, sabkx, amirhsz, megarnie

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)$

Because $a_i,b_i\ge \dfrac{1}{2}$ for infinitely many $i$ , 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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

JackXD

151 posts

JackXD

#5 h Aug 12, 2015, 8:26 PM • 2 Y

Y by Adventure10, Mango247

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.

This post has been edited 2 times. Last edited by JackXD, Aug 12, 2015, 8:28 PM
Reason: xx

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

leminscate

109 posts

leminscate

#6 h Jun 6, 2016, 9:32 AM • 2 Y

Y by Adventure10, Mango247

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)$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bobthesmartypants

4337 posts

bobthesmartypants

#7 h Sep 25, 2016, 12:25 AM • 1 Y

Y by Adventure10

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

math163

58 posts

math163

#8 h Sep 9, 2017, 6:45 AM • 4 Y

Y by Iustin444, test20, Anar24, Adventure10

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

lifeisgood03

388 posts

lifeisgood03

#9 h Aug 22, 2018, 8:24 PM • 2 Y

Y by Adventure10, Mango247

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pad

1671 posts

pad

#10 h Aug 3, 2019, 10:01 PM • 2 Y

Y by Adventure10, Mango247

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$

Remarks

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

This post has been edited 2 times. Last edited by pad, Aug 3, 2019, 10:07 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

math_pi_rate

1218 posts

math_pi_rate

#13 h May 4, 2020, 9:26 PM • 1 Y

Y by amar_04

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$

This post has been edited 1 time. Last edited by math_pi_rate, May 4, 2020, 9:34 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

yayups

1614 posts

yayups

#14 h Jul 8, 2020, 6:45 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

TheUltimate123

1740 posts

TheUltimate123

#15 h Oct 7, 2020, 4:34 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

v_Enhance

6882 posts

v_Enhance

#16 h Apr 10, 2021, 2:06 AM • 1 Y

Y by HamstPan38825

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.

This post has been edited 2 times. Last edited by v_Enhance, Apr 10, 2021, 2:09 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AwesomeYRY

579 posts

AwesomeYRY

#17 h Jun 25, 2021, 12:15 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Spacesam

596 posts

Spacesam

#18 h Jun 27, 2021, 6:34 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mathleticguyyy

3217 posts

mathleticguyyy

#19 h Aug 29, 2021, 9:58 PM

Y by

$|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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

HamstPan38825

8881 posts

HamstPan38825

#22 h Oct 11, 2021, 5:42 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pad

1671 posts

pad

#23 h Dec 8, 2021, 11:42 PM

Y by

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$ .

Motivation

This post has been edited 5 times. Last edited by pad, Dec 9, 2021, 1:33 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cj13609517288

1934 posts

cj13609517288

#24 h May 23, 2022, 7:31 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

awesomeming327.

1746 posts

awesomeming327.

#25 h Jul 29, 2022, 2:46 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Inconsistent

1455 posts

Inconsistent

#26 h Aug 19, 2022, 6:19 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

NTistrulove

183 posts

NTistrulove

#27 h Oct 24, 2022, 10:18 AM

Y by

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$ .

This post has been edited 2 times. Last edited by NTistrulove, Oct 24, 2022, 12:47 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

IAmTheHazard

5005 posts

IAmTheHazard

#28 h Mar 11, 2023, 9:09 PM • 1 Y

Y by centslordm

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

IAmTheHazard

5005 posts

IAmTheHazard

#29 h Mar 11, 2023, 9:12 PM • 1 Y

Y by centslordm

NTistrulove wrote:

Long

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 post has been edited 1 time. Last edited by IAmTheHazard, Mar 11, 2023, 9:13 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

GrantStar

821 posts

GrantStar

#30 h Mar 16, 2023, 7:19 PM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Mogmog8

1080 posts

Mogmog8

#31 h Apr 15, 2023, 4:50 AM • 1 Y

Y by centslordm

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cursed_tangent1434

662 posts

cursed_tangent1434

#33 h Oct 1, 2023, 12:49 AM • 1 Y

Y by Shreyasharma

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Ywgh1

139 posts

Ywgh1

#34 h Oct 10, 2023, 1:31 PM

Y by

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.

This post has been edited 1 time. Last edited by Ywgh1, Oct 10, 2023, 1:32 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AngeloChu

471 posts

AngeloChu

#35 h Oct 10, 2023, 10:35 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

joshualiu315

2534 posts

joshualiu315

#36 h Oct 16, 2023, 2:26 AM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

spectator01

60 posts

spectator01

#37 h Nov 19, 2023, 9:35 PM

Y by

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

eibc

600 posts

eibc

#38 h Jan 4, 2024, 1:15 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

blueprimes

363 posts

blueprimes

#39 h Jan 21, 2024, 12:59 PM

Y by

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.

This post has been edited 4 times. Last edited by blueprimes, Jan 22, 2024, 1:14 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

asdf334

7585 posts

asdf334

#40 h Apr 22, 2024, 1:08 AM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MathWithAnE

7 posts

MathWithAnE

#41 h Sep 12, 2024, 5:22 PM

Y by

Super scuffed solution

Click to reveal hidden text

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

onyqz

195 posts

onyqz

#42 h Dec 14, 2024, 11:28 PM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Mquej555

15 posts

Mquej555

#43 h Jan 10, 2025, 3:27 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

megarnie

5610 posts

megarnie

#44 h Apr 8, 2025, 2:44 AM • 1 Y

Y by neeyakkid23

Solved with neeyakkid23.

Suppose for some $a,b$ that this was not the case. Since $f$ has no fixed points, we have $(a_n - a_{n-1}) (b_n - b_{n-1}) > 0 \ \forall n \in \mathbb N$
This means that either $a_{n-1}, b_{n-1} < \frac 12, a_n = a_{n-1} + \frac 12,$ and $b_n = b_{n-1} + \frac 12$ , or $a_{n-1}, b_{n-1} \ge \frac 12, a_n = a_{n-1}^2$ , and $b_n = b_{n-1}^2$ .

The key is to consider the quantity $b_n - a_n$ and denote this as $c_n$ . The above results imply that if $a_{n-1}, b_{n-1} < \frac 12$ , then $c_n = c_{n-1}$ and if $a_{n-1}, b_{n-1} \ge \frac 12$ , then $c_n = c_{n-1} (a_{n-1} + b_{n-1})$ , so in particular $(c_i)$ is nondecreasing.

Claim: There are infinitely many positive integers $i$ where $b_i < \frac{9}{16}$ .
Proof: Suppose otherwise. Then fix $M$ so that all $i \ge M$ satisfy $b_i < \frac{9}{16}$ . Consider any $i \ge M$ where $b_i \ge \frac 12$ (obviously exists). Note that $b_{i + 1}$ is less than or equal to $\left( \frac{9}{16} \right)^2 < \frac 12$ and it is greater than or equal to $\frac 14$ , so $b_{i + 2} = b_{i + 1} + \frac 12 \ge \frac 34 > \frac{9}{16}$ , a contradiction. $\square$

The claim implies that there are infinitely many positive integers $i$ where $c_{i + 1} > c_i \left( \frac 12 + \frac{9}{16} \right) = c_i \cdot \frac{17}{16}$ . Let $S = i_1, i_2, \ldots,$ be the sequence of such $i$ .

For any positive integer $N$ , fix $n > i_N$ . Since $\frac{c_{k + 1}}{c_k} \ge 1$ always, we have $c_n = c_1 \prod_{i=1}^{n-1} \frac{c_{i + 1}}{c_i} \ge \prod_{k=1}^N \frac{c_{i_k + 1}}{c_{i_k}} > c_1 \left( \frac{17}{16} \right)^N$ Taking $N$ arbitrarily large implies that there exists $n$ so that $c_n > 1434$ , which is impossible as $c_n = b_n - a_n$ is upper bounded by $1$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

math-olympiad-clown

49 posts

math-olympiad-clown

#45 h Apr 9, 2025, 3:26 PM

Y by

is this okay? :wacko:

We want to show that there exists an integer $n \in \mathbb{N}$ such that
$(a_n - a_{n-1})(b_n - b_{n-1}) < 0.$ It is easy to observe that: $a_n - a_{n-1} < 0$ if $a_{n-1} > \frac{1}{2}$ ,
$a_n - a_{n-1} > 0$ if $a_{n-1} < \frac{1}{2}$ .
First, consider the case where $0 < a < \frac{1}{2} < b < 1$ . In this case, $a_1$ and $b_1$ will undergo different operations (i.e., squaring vs. adding $\frac{1}{2}$ ), so the condition is immediately satisfied.
Now, it remains to consider the cases: $0 < a < b < \frac{1}{2}$ , $\frac{1}{2} < a < b < 1$ .
By symmetry of the recurrence structure, it suffices to analyze case (i).
Let us take a specific example to gain insight. Suppose $a_0 = 0.3$ . Then, by iterating the recurrence:
$a_0 = 0.3,\quad a_1 = 0.3 + \frac{1}{2} = 0.8,\quad a_2 = 0.8^2 = 0.64,\quad a_3 = 0.64^2 \approx 0.4096,\quad \dots$ Eventually, we observe that the number of steps during which $a_n \in \left[\frac{1}{2}, 1\right)$ becomes relevant. To analyze this further, we divide the interval $\left[\frac{1}{2}, 1\right)$ into infinitely many subintervals using the roots of: $x + \frac{1}{2} = \left( \frac{1}{2} \right)^{\frac{1}{2^n}},\quad n = 1, 2, 3, \dots$ Now, any two sequences $a_n$ and $b_n$ must lie in the same subinterval at every step to avoid differing in their behavior within $\left[\frac{1}{2}, 1\right)$ , because if not, they will not remain in that range for the same number of steps, and this will eventually result in $(a_n - a_{n-1})(b_n - b_{n-1}) < 0.$ Next, we prove that $a_n$ and $b_n$ cannot remain in the same subinterval forever. Let $c_n = b_n - a_n > 0.$ If both $a_n$ and $b_n$ undergo the $+\frac{1}{2}$ operation, then clearly $c_{n+1} = c_n$ .
However, if both undergo the squaring operation, then:
$a_{n+1} = a_n^2,\quad b_{n+1} = b_n^2 = (a_n + c_n)^2 = a_n^2 + 2a_n c_n + c_n^2,$ so
$c_{n+1} = b_{n+1} - a_{n+1} = 2a_n c_n + c_n^2 > 0,$ i.e., the gap between the two sequences increases.
Note that after a $+\frac{1}{2}$ operation, a squaring operation must eventually occur (to avoid surpassing 1). Thus, the sequences must be squared infinitely many times, causing the gap to increase indefinitely.
Therefore, for sufficiently large $n$ , the sequences $a_n$ and $b_n$ will eventually fall into different subintervals. At that point, they must undergo different operations, which implies:
$(a_n - a_{n-1})(b_n - b_{n-1}) < 0.$ Hence, we conclude that there exists a positive integer $n$ such that: $(a_n - a_{n-1})(b_n - b_{n-1}) < 0.$

This post has been edited 5 times. Last edited by math-olympiad-clown, May 29, 2025, 4:21 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ezpotd

1328 posts

ezpotd

#46 h May 17, 2025, 7:23 AM

Y by

Assume this is not true. $a_n - a_{n - 1}$ positive implies $a_{n - 1} < \frac 12$ , and vice-versa. Thus $a_n, b_n$ are always either both greater or less than $\frac 12$ . We now prove that the claim being false implies that $c_n = a_n -b_n$ is unbounded, which finishes.

Claim: For $n > 0$ , $\min(a_n), \min(b_n) \ge \frac 14$ .
Proof: Output of $f$ in either case is at least $\frac 14$ .

Obviously, we must have $a_n \ge \frac 34 > \frac 12 > a_{n - 1}$ infinitely many times, in that scenario we have $c_{n - 1} = c_n , c_{n + 1} = a_n^2 - b_n^2 = (a_n +b_n)(a_n - b_n)$ , by the above claim this gives $c_{n + 1} \ge \frac 32 c_n$ . We can observe that $c_n$ is similarly nondecreasing (if $a_n, b_n < \frac 12$ it is obviously constant, if they are at least $\frac 12$ difference of squares finishes again), so $c_n$ increases by a factor of $\frac 32$ infinitely times, so it is unbounded, impossible.

Z K Y

N Quick Reply