Can arbitrary values be reached by repeatedly adding or subtracting a fixed percentage of the current value?

Let $p\in(0,1)$ such that $\frac{\ln(1+p)}{\ln(1-p)}$ is irrational.

For $(a,b,c)\in\Bbb N^3$ with $b<c$, let $$ F(a,b,c)=\begin{cases}\bigl(\lfloor (1+p)a\rfloor, b, c\bigr)&\text{if }a<b,\\ \bigl(a,\lceil\frac b{1-p}\rceil, \lceil\frac c{1-p}\rceil\bigr)&\text{if } c\le a,\\(a,b,c)&\text{if }b\le a<c \end{cases}$$

Theorem. If $a,b,c\in\Bbb N$ with $b<c$, then the sequence $\{F^{\circ n}(a,b,c)\}_n$ is eventually stationary.

[Incomplete] Proof. Let $(a_n,b_n,c_n)=F^{\circ n}(a,b,c)$. If ever $b_n\le a_n<c_n$, we are done. If $a_0<\frac1p$ and ever $b_n>a_n$ for the first time, then $a_n=a_0$ and $\lfloor(1+p)a_n\rfloor = a_n$ and we are done. So assume otherwise.$a_0\ge \frac 1p$ and never $b_n\le a_n<c_n$. As $\lceil\frac c{1-p}\rceil \ge \frac c{1-p}>b$, we will eventually have $c_n>a_n$ and hence $a_n<b_n$ for some $n$. Thus $F$ takes the first branch infinitely often and $a_n\to +\infty$. But then also $b_n\to+\infty$ and $c_n\to+\infty$.

Claim: $q:=\liminf\frac{c_n}{b_n}>1$. (???)

Now let $x_n=\frac{a_n}{b_n}$. Then we have $$x_{n+1}\approx \begin{cases}(1+p)x_n&\text{if }x_n<1\\(1-p)x_n&\text{if }x_n>1\end{cases}$$ and the error hidden in the "$\approx$" tends to $0$ as $n\to\infty$. As $\frac{\ln(1+p)}{\ln(1-p)}$ is irrational, this implies that infintiely many $x_n$ are close to any given $\alpha$ with $1<\alpha<1+p$. In particular, we will find ininfitely mayn $n$ with $1<x_n<\frac{1+q}2$, hence some $n$ with $1<\frac {a_n}{b_n}<\frac{c_n}{b_n}$. Then $F(a_n,b_n,c_n)=(a_n,b_n,c_n)$. $\square$(modulo claim)

Corollary. If $X,G\in \Bbb N$ and $X\ge\frac 1p$, then a finite sequence of applications of $f_+\colon x\mapsto \lfloor (1+p)x\rfloor$ and/or $f_-\colon x\mapsto \lfloor (1-p)x\rfloor$ takes $X$ to $G$.

Proof. Let $(a_0,b_0,c_0)=(X,G,G+1)$ and define recursively $(a_{n+1},b_{n+1},c_{n+1})=F(a_n,b_n,c_n)$. by the theorem above, there is some minimal $n$ with $(a_{n+1},b_{n+1},c_{n+1})=(a_{n},b_{n},c_{n})$. As $F$ is component-wise non-decreasing, we conclude $a_n\ge a_{n-1}\ge\ldots \ge X$, and $b_n\ge \ldots \ge G$. From $a_n\ge \frac1p$, we see $\lfloor (1+p)a_n\rfloor \ge a_n+1$, hence $F(a_n,b_n,c_n)=(a_n,b_n,c_n)$ implies $a_n\ge b_n$. Likewise. $\lceil\frac {b_n}{1-p}\rceil >b_n$ implies that $c_n>a_n$, so that $b_n\le a_n<c_n$.

Whenever $F(a_n,b_n,c_n)$ takes the first branch, we have $a_{n+1}=f_+(a_n)$. Note that $f_-(x)\ge y\iff x\ge \frac y{1-p}$; hence whenever $F(a_n,b_n,c_n)$ takes the second branch, we have $b_n\le f_-(x)<c$ for all $x$ with $b_{n+1}\le x<c_{n+1}$. Let $k=\{\,i\mid 0\le i<n,a_{i+1}>a_i\,\}$. Then $f_+^{\circ k}(a_0)=a_n$ and $b_0\le f_-^{\circ(n-k)}(x)<c_0$ whenever $b_n\le x<c_n$. So from $b_n\le a_n<c_n$ we conclude $$f_-^{\circ(n-k)}f_+^{\circ k}(X)=G.$$ $\square$

Tags:

Percentages