IMO Shortlist 2014 A2

Art of Problem Solving

AoPS Online

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

M

IMO Shortlist 2014 A2

G H J

Reveal topic tags

L

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.

209 posts

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

233 posts

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

1135 posts

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

409 posts

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

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.

109 posts

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

58 posts

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

388 posts

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

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.

1218 posts

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

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.

1740 posts

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

6877 posts

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

579 posts

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

596 posts

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

3217 posts

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

8866 posts

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

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.

1922 posts

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

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

1455 posts

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

183 posts

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

5003 posts

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

5003 posts

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

821 posts

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

1080 posts

#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

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

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.

471 posts

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

2534 posts

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

60 posts

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

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.

355 posts

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

7585 posts

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

7 posts

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

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.

15 posts

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

5610 posts

#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

31 posts

math-olympiad-clown

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

Y by

Is this ok? :wacko:

:wacko:

We want to conclude that there exist a "n" such that $(a_n - a_{n-1}) (b_n - b_{n-1}) < 0 \ \forall n \in \mathbb N$ and it's easy to see that
$a_{n}$ - $a_{n-1}$ <0 if $a_{n-1}$ >1/2 and $a_{n}$ - $a_{n-1}$ >0 if $a_{n-1}$ <0.

First,we can easily figure out that 0<a<1/2<b will immediately finish the discussion
because $a_{1}$ and $b_{1}$ will do different operations.

So the remain cases are 0<a<b<1/2 or 1/2<a<b<1. and eventually we can see we only need to discuss about
the first case.

Now let's take some number for finding inspiration, ex: a=0.3 then we proceed the process:
0.3,0.8,0.64,0.409..,0.9...,0.8 now we know that how many times did a stay at the interval [1/2,1) is important.
and we can separate the interval [1/2,1) by using the roots of
$\left(x + \frac{1}{2}\right) = \left(\frac{1}{2}\right)^{\frac{1}{2^n}}$ for n=1,2,3.......

Then we can separate the interval [1/2,1) into Infinitely many subintervals. and at any time, An and Bn should stay in the same subinterval because if not they won't stay at [1/2,1) for the same times and will ultimately leads to ( $a_{n}$ - $a_{n-1}$ )( $b_{n}$ - $b_{n-1}$ )<0.

Now we need to do is to prove $a_{n}$ and $b_{n-1}$ can not stay in the same small interval forever.
Let $b_{0}$ - $a_{0}$ = $c_{0}$ > 0, now we define $b_{n}$ - $a_{n}$ = $c_{n}$ for all n's.
if $b_{n}$ and $a_{n}$ both increase by 1/2 then obviously $c_{n+1}$ = $c_{n}$ ,but if $b_{n+1}$ = $b_{n}^2$ = $($ a_{0} $+$ c_{0} $)^2$ and $a_{n+1}$ = $a_{n}^2$
then $c_{n+1}$ - $c_{n}$ = $c_{n}^2$ +2* $c_{n}$ * $a_{n}$ >0.that means the gap of two sequence A and B increases, and it's easy to see that we have to do the "squaring operation" for infinietly times because after a "+1/2" operaion we must do a "squaring operation" .

Then we can always find a sufficiently large n that two sequence are in different subinterval
SO WE CAN CONCLUDE THERE'S ALWAYS A "N" FOR $(a_n - a_{n-1}) (b_n - b_{n-1}) < 0 \ \forall n \in \mathbb N$ !

This post has been edited 3 times. Last edited by math-olympiad-clown, Apr 9, 2025, 3:37 PM

Z K Y

The post below has been deleted. Click to close.

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

1277 posts

ezpotd

#46 h Today at 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

G

H

=

© 2025 AoPS Incorporated

a