2
$\begingroup$

The following question is from a contest in my city in the year 2018 (sorry if the wording is bad, I translated this from my language):

The numbers $a_0,a_1,\dots$ are formed such that $a_0$ is a positive integer and $a_{n+1}$ is either equal to $2a_n+1$ or equal to $\frac{a_n}{a_n+2}$ for any $n\geq 0$. Decide if there exists a number $k\geq1$ such that $a_k=2018$.

I tried working backwards. If $a_n=x$, then $a_{n-1}$ is either $\frac{x-1}{2}$ or $\frac{2x}{1-x}$. By this I can say if $a_k=2018$, then $a_{k-1}$ is either $\frac{2017}{2}$ or $-\frac{4036}{2017}$. But we can't get negative values. So we can ignore the second value and continue working backwards and take only the first value. But we cannot get a positive integer at the last. So such $k$ cannot exist.

Is this a right solution?

$\endgroup$
2
  • 1
    $\begingroup$ Notice that when $x<1$, you will get $\frac{2x}{1-x}$ as a positive number. By working backwards, you will eventually reach such an $x$. So you can't just ignore the second value in all cases. $\endgroup$
    – Oshawott
    Oct 12, 2021 at 13:08
  • $\begingroup$ On AoPS: artofproblemsolving.com/community/c6h1071763p4663881. $\endgroup$
    – Martin R
    Oct 12, 2021 at 13:53

1 Answer 1

5
$\begingroup$

For a given odd integer $N > 1$, we let $S_N$ denote the set $\{\frac x y: x, y \in \Bbb Z_{> 0}, \gcd(x, y) = 1, x + y = N\}$.

We define two functions $f, g$ on $S_N$ as follows.

If $\frac x y \in S_N$ with $x > y$, then $f(\frac xy) = \frac{x - y}{2y}$; if $\frac xy \in S_N$ with $x < y$, then $f(\frac xy) = \frac{2x}{y - x}$.

If $\frac xy \in S_N$ with $y$ even, then $g(\frac xy) = \frac{x + \frac y2}{\frac y2}$; if $\frac xy \in S_N$ with $x$ even, then $g(\frac xy) = \frac{\frac x2}{\frac x2 + y}$.

It is easy to check that $f$ and $g$ are both maps from $S_N$ to $S_N$, and they are inverses of each other.

Note also that for any $a \in S_N$, $g(a)$ is either $2a + 1$ or $\frac a{a + 2}$.


Since $S_N$ is a finite set, we know that $g$ is just a permutation of that set. This means that for any element $a \in S_N$, there exists $k \in \Bbb Z_{> 0}$ such that $g^{(k)}(a) = a$, where $g^{(k)}$ denotes the $k$-th iteration of $g$.

Now take $N = 2019$ and $a = \frac {2018}1$. We have seen that there exists $k \in \Bbb Z_{> 0}$ such that $g^{(k)}(2018) = 2018$.

We then simply define $a_i = g^{(i)}(2018)$ for $i = 0, \dots, k$.


This leads to the following sequence:

$2018, 1009/1010, 1514/505, 757/1262, 1388/631, 694/1325, 347/1672, 1183/836, 1601/418, 1810/209, 905/1114, 1462/557, 731/1288, 1375/644, 1697/322, 1858/161, 929/1090, 1474/545, 737/1282, 1378/641, 689/1330, 1354/665, 677/1342, 1348/671, 674/1345, 337/1682, 1178/841, 589/1430, 1304/715, 652/1367, 326/1693, 163/1856, 1091/928, 1555/464, 1787/232, 1903/116, 1961/58, 1990/29, 995/1024, 1507/512, 1763/256, 1891/128, 1955/64, 1987/32, 2003/16, 2011/8, 2015/4, 2017/2, 2018$

$\endgroup$
1
  • $\begingroup$ +1 interesting argument and it does work. $\endgroup$ Oct 12, 2021 at 14:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .