Suppose $\frac{1}{2} < s < 1$ . An insect flying on $[0,1]$ . If it is on point $a$ , it jump into point $ a\times s$ or $(a-1) \times s +1$ . For every real number $0 \le c \le 1$, Prove that insect can jump that after some jumps , it has a distance less than $\frac {1}{1402}$ from point $c$. Proposed by Navid Safaei
Problem
Source: Iran TST 2023 ; Exam 2 Problem 2
Tags: Iran, TST, Iranian TST, combinatorics
17.03.2023 03:59
Lemma: $\forall(l, r)\subset[0, 1],\ \exists m\geq0$ and $a_0, a_1, \dots, a_m\in\{0, 1\}$ s.t. $(1-s)\sum_{i=0}^ma_is^i\in(l, r)$. Proof: Let's recursively construct $a_k$ as follow: $a_k:=\begin{cases} 1\text{, if }(1-s)(s^k+\sum_{i=0}^{k-1}a_is^i)<r\\ 0\text{, otherwise} \end{cases}$ Induction on $k$ to prove that $0<r-(1-s)\sum_{i=0}^ka_is^i\leq s^{k+1}$. For $k=0$, if $1-s<r$, then $a_0=1$, $0<r-(1-s)a_0\leq 1-1+s=s$; otherwise $a_0=0$, $0<r\leq1-s\overset{s>\frac12}\leq s$. $\therefore$ the inequality holds when $k=0$. Suppose for $k=k'$, the inequality holds, $0<r-(1-s)\sum_{i=0}^{k'}a_is^i\leq s^{k'+1}$. For $k=k'+1$, if $(1-s)(s^{k'+1}+\sum_{i=0}^{k'}a_is^i)<r$, then $a_{k'+1}=1$, $0<r-(1-s)\sum_{i=0}^{k'+1}a_is^i\leq s^{k'+1}-(1-s)s^{k'+1}=s^{k'+2}$; otherwise $a_{k'+1}=0$, $0<r-(1-s)\sum_{i=0}^{k'+1}a_is^i\leq(1-s)s^{k'+1}\overset{s>\frac12}\leq s^{k'+2}$. $\therefore$ the inequality holds when $k=k'+1$. $\therefore$ by induction $\forall k,\ 0<r-(1-s)\sum_{i=0}^ka_is^i\leq s^{k+1}$. $\Rightarrow$ take $m\geq\log_s(r-l)$ and we get $0<r-(1-s)\sum_{i=0}^ma_is^i\leq s^{m+1}\leq s(r-l)<r-l$. $\Rightarrow(1-s)\sum_{i=0}^ma_is^i\in(l, r)$, and we finish the lemma. At first, no matter where the insect is, $\forall\epsilon>0$, the insect can jump into $b\in(0, \epsilon)$ by jumping into $a\times s$ for several times since $\lim_{n\to\infty}as^n=0$. For any interval $(l, r)$, construct $a_0, a_1, \dots, a_m$ as that in the lemma such that $(1-s)\sum_{i=0}^ma_is^i\in(l, r)$. Start from $b$ and do $m+1$ jumps, the $i$-th jump jump into $a\times s$ if $a_{m+1-i}=0$, and into $(a-1)\times s+1$ otherwise. The position after all jumps are done is $bs^{m+1}+(1-s)\sum_{i=0}^ma_is^i$. Take $\epsilon<r-(1-s)\sum_{i=0}^ma_is^i$, and the position after all jumps $<r$. Since $bs^{m+1}$ is positive, the position after all jumps $>l$. $\therefore$ the position after all jumps $\in(l, r)$. Take $l=\max(0, c-\frac1{1402}), r=\min(1, c+\frac1{1402})$ and we're done.
24.03.2023 22:11
I hope this is right. The key thing is problem is symmetric to points $0$ and $1$ since moves are $|0-a|\rightarrow |0-as|$ or $|1-a|\rightarrow |1-as|$ Lets restate the problem. $\frac{1}{2} < s < 1$ is a real number. There is a point in $[0,1]$. We apply homothety with ratio s on the points and the center is either $0$ or $1$. Prove that we can get in any interval in $[0,1]$ $Proof:$ First notice that we can get as close as we want to points $0$ and $1$ since $s<1$. Say that we want to get in interval $I$. We will move backwards and in each move we will apply homothethy with ratio $1<\frac{1}{s}<2$ with center either $0$ or $1$. If transformed interval contains any point that our point can get into we are done by following steps backwards. We will show that our transformed interval will contain either $0$ or $1$. We apply the following strategy: 1) If $ I \cap [0,\frac{1}{2}]\neq \varnothing$ Then we apply homothety with center $0$ and the ratio is $\frac{1}{s}$. $I\rightarrow I'$ 2) Otherwise apply homothety with center $1$ with ratio $\frac{1}{s}$. $I\rightarrow I'$ We apply this succesively. Since in the beginning $I\cap [0,1]\neq \varnothing$ and $s<2 \Rightarrow I' \cap [0,1] \neq \varnothing$ At any time if $I$ contains $0$ or $1$ we stop the algorithm and we are done. Otherwise, this means $I$ doesn't get outside the interval $[0,1]$ but this is a contradiction since each time the length of $I$ is multiplied by $s>1$ Q.E.D.
30.06.2023 19:39
Wow, again another beautiful problem. Guess who was the proposer? Yeah, Mr. Safaei I think we can change the name of this year TST to Navid's Exam you already proposed $5$ out of $12$ problems. Oh, dam* man it's unbelievable. Anyway, I didn't think on the problem yet, I just read it and enjoyed. As I scammed the posts, very fast I didn't any solution with the fact that we can decrease the distance of point $a$ with point $c$ in each step. I think it will be useful; I try to find a solution relevant to this idea. I hope I can find!
01.07.2023 01:59
So, it seems like that my thought was correct. I didn't write the accurate answer, just the idea. Replace $a$ with $as$ every time. It's clear that the distance between $a$ and $c$ will decrease every time. Continue this process, there is one of the $2$ state will be happen: $1.$ After a while the distance of between two points will be less than the $\frac{1}{1402}$ and we are done. $2.$ After a while there exists jump that the distance of $A$ from $b$ will increase according to the previous jump, in this case replace $a$ with $(a-1)s+1$ and continue the process. It is clear that we are decreasing the distance of $A$ and $c$ so we know that there exists a jump that the distance between $A$ and $c$ is smaller than $\frac{1}{1402}.$ So are done. P.S: We define the last point as $A.$