Initially, Alice is given a positive integer $a_0$. At time $i$, Alice has two choices, $$\begin{cases}a_i\mapsto\frac1{a_{i-1}}\\a_i\mapsto2a_{i-1}+1\end{cases}$$Note that it is dangerous to perform the first operation, so Alice cannot choose this operation in two consecutive turns. However, if $x>8763$, then Alice could only perform the first operation. Determine all $a_0$ so that $\{i\in\mathbb N\mid a_i\in\mathbb N\}$ is an infinite set.
Problem
Source: IMOC 2019 N5
Tags: number theory, Sequences
28.08.2021 12:45
The idea is quite similar to this. The answer is all positive even integer less than or equal to $17526=2 \cdot 8763$. Let $b_i=\frac{1}{a_i+1} \in (0,1)$. The operation $a_i=\frac{1}{a_{i-1}}$ or $a_i=2a_{i-1}+1$ can be written as $b_i=1-b_{i-1}$ or $b_i=\frac{1}{2} b_{i-1}$. Note that except possible $a_0$, all integers in $\{ a_i \}$ are no more than $2 \cdot 8763+1$. As there are infinitely many positive integer $a_i$, there must be a positive integer $k$ appears at least twice. Hence there is a cycle in the sequence. Claim. $k$ is even. Moreover, for any even integer $k$, the cycle is unique. For brevity's sake, let $a_0=k$ (the index $0$ here is not important). Then $b_0=\frac{1}{k+1}$. Observe that if $b_i=\frac{p}{q}$ is the reduced form, then the first operation $b_{i+1}=1-b_i=\frac{q-p}{q}$ does not change the denominator; the second operation $b_{i+1}=\frac{1}{2} b_i=\frac{p}{2q}=\frac{p/2}{q}$ will double the denominator if $p$ is odd, and does not change the denominator if $p$ is even. Thus the denominator is non-decreasing. Because $a_i=k$ appears later, i.e. $b_i=\frac{1}{k+1}$ appears later, the denominator must be constant in the cycle. In other word, we cannot use the second operation if $p$ is odd. Now if $k$ is odd, we have $b_1=\frac{1}{k+1}$, we can only apply the first operation, so $b_2=\frac{k}{k+1}$. Again, we have to apply the first operation. But we cannot use the first operation in two consecutive turns, a contradiction. If $k$ is even, an extra restriction is that if $b_i=\frac{p}{k+1}$ and $p$ is even, then we must apply the second operation. It's because if we apply the first operation, then $b_{i+1}=1-b_i=\frac{k+1-p}{k+1}$, the numerator is odd, so we have to apply the first operation again, contradiction. Therefore the sequence is uniquely determined: if the numerator is odd, apply the first operation; if the numerator is even, apply the second operation. Initially, $b_0=\frac{1}{k+1}$, where $1 \equiv 2^{\varphi(k+1)} \pmod{k+1}$. If $b_i=\frac{a}{k+1}$ where $a \equiv 2^r \pmod{k+1}$, consider two cases: If $a$ is even, $b_{i+1}=\frac{1}{2} b_i=\frac{a/2}{k+1}$, where $a/2 \equiv 2^{r-1} \pmod{k+1}$. If $a$ is even, then $b_{i+1}=1-b_i=\frac{k+1-a}{k+1}$, $b_{i+2}=\frac{1}{2} b_{i+1}=\frac{(k+1-a)/2}{k+1}$, $b_{i+3}=1-b_{i+2}=\frac{(k+1+a)/2}{k+1}$, where $(k+1+a)/2 \equiv 2^{r-1} \pmod{k+1}$. Therefore, we will finally reach $b_i=\frac{2^0}{k+1}=\frac{1}{k+1}$, as desired. The claim is proved. $\blacksquare$ Back to the main problem. If $a_0$ is odd, then $b_0=\frac{1}{a_0+1}$ has an even denominator. Two operations either double the denominator or keep it the same, hence it's impossible that $b_i=\frac{1}{k+1}$ where $k$ is even. If $a_0$ is even and $a_0>17526$, then $b_0=\frac{1}{a_0+1}$ has an odd denominator. Because $b_i=\frac{1}{k+1}$ where $k+1$ is odd, we must have $a_0=k$. Due to the claim, the cycle is uniquely determined, and $2^{\varphi(k+1)}, \ldots, 2^1,2^0$ all appeared in the numerator. But when $b_i=\frac{2}{k+1}$, we need to use the second operation, which is prohibited as $a_i=\frac{k-1}{2}>8763$. If $a_0$ is even and $a_0 \le 17526$, the cycle in the claim is always possible, producing a periodic sequence with $k$ appears infinitely many times. In conclusion, the answer is all positive even integer less than or equal to $17526=2 \cdot 8763$.